[프로그래머스] 블록 이동하기 (C++)

https://programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

#include <string>
#include <vector>
#include <cstring>
#include <queue>
#include <algorithm>
using namespace std;

int dx[4]={-1,1,0,0};
int dy[4]={0,0,-1,1};

struct Robot{
    pair<int,int> a;
    pair<int,int> b;
    int cnt;
};

int solution(vector<vector<int>> board) {
    int answer = 0;
    int N=board.size()-1;
    bool visited[101][101][101][101];
    memset(visited, false, sizeof(visited));
    queue<Robot> q;
    q.push({{0,0},{0,1},0});
    visited[0][0][0][1]=true;
    while (!q.empty()){
        Robot r=q.front();
        q.pop();
        int x1=r.a.first;
        int y1=r.a.second;
        int x2=r.b.first; 
        int y2=r.b.second;
        int dist=r.cnt;
        if ((x1==N && y1==N) || (x2==N && y2==N)){
            answer=dist;
            break;
        }
        for (int i=0; i<4; i++){
            int nx1=x1+dx[i];
            int ny1=y1+dy[i];
            int nx2=x2+dx[i];
            int ny2=y2+dy[i];
            if (nx1<0 || ny1<0 || nx2<0 || ny2<0 || nx1>N || ny1>N || nx2>N || ny2>N)
                continue;
            if (!visited[nx1][ny1][nx2][ny2] && board[nx1][ny1]==0 && board[nx2][ny2]==0){
                visited[nx1][ny1][nx2][ny2]=true;
                q.push({{nx1,ny1}, {nx2,ny2}, dist+1});
            }
        }
        if (y2-y1==1){          //가로
            if (x1>0 && board[x1-1][y1]==0 && board[x1-1][y1+1]==0){
                if (!visited[x1-1][y1][x1][y1]){
                    visited[x1-1][y1][x1][y1]=true;
                    q.push({{x1-1,y1},{x1,y1},dist+1});
                }
                if (!visited[x1-1][y1+1][x2][y2]){
                    visited[x1-1][y1+1][x2][y2]=true;
                    q.push({{x1-1,y1+1},{x2,y2},dist+1});
                }
            }  
            if (x1<N && board[x1+1][y1]==0 && board[x1+1][y1+1]==0){
                if (!visited[x1][y1][x1+1][y1]){
                    visited[x1][y1][x1+1][y1]=true;
                    q.push({{x1,y1},{x1+1,y1}, dist+1});
                }
                if (!visited[x2][y2][x1+1][y1+1]){
                    visited[x2][y2][x1+1][y1+1]=true;
                    q.push({{x2,y2},{x1+1,y1+1},dist+1});
                }
            }
        }
        else if (x2-x1==1){     //세로
            if (y1>0 && board[x1][y1-1]==0 && board[x1+1][y1-1]==0){
                if (!visited[x1][y1-1][x1][y1]){
                    visited[x1][y1-1][x1][y1]=true;
                    q.push({{x1,y1-1}, {x1,y1}, dist+1});
                }
                if (!visited[x1+1][y1-1][x2][y2]){
                    visited[x1+1][y1-1][x2][y2]=true;
                    q.push({{x1+1,y1-1}, {x2,y2}, dist+1});
                }
            }
            if (y1<N && board[x1][y1+1]==0 && board[x1+1][y1+1]==0){
                if (!visited[x1][y1][x1][y1+1]){
                    visited[x1][y1][x1][y1+1]=true;
                    q.push({{x1,y1},{x1,y1+1}, dist+1});
                }
                if (!visited[x2][y2][x1+1][y1+1]){
                    visited[x2][y2][x1+1][y1+1]=true;
                    q.push({{x2,y2}, {x1+1,y1+1}, dist+1});
                }
            }
        }
    }
    return answer;
}

상당히 까다로운 문제였다 .. 거의 하드코딩으로 푼 듯..ㅜㅜ

 

로봇은 항상 수평, 또는 수직으로만 놓이기 때문에, 충돌 확인을 해야 하는 후보칸은 회전축을 기준으로 대각선 방향에 있는 칸 4개입니다. 

-> 90도 회전 하려면 가로 방향이면 위, 아래 가로방향이 비어있는지 확인 , 세로 방향이면 왼, 오 세로방향이 비어있는지 확인해야 한다. 한쪽이 모두 비어있어야 회전이 가능하다.

 

방문 표시를 4차원 배열 이용해서 했다. 사실 [x][y][direction] 이렇게 하는 방법도 있겠다. 푸는 거에 집중하느라 최적화는 하지 못했다.