[BFS] 블록 이동하기 - 2020 카카오 블라인드 채용

물체가 보드의 2칸을 차지하는 유형의 BFS 문제다.

BFS 문제들 중에서는 꽤 난이도가 있는 문제였던 것 같다.

 

 

해결 방법

2x1 크기를 차지하는 로봇에 대한 구조체를 {좌표1, 좌표2, BFS 깊이}로 구성하여 생성했다.

이렇게 좌표 2개를 동시에 따지면 로봇이 가로로 서있는지, 세로로 서있는지, 어느 방향으로 서있는지 고려할 필요 없다.

또 BFS에서 방문 여부를 검사할 때도 좌표 2개를 동시에 따져야 한다. 그래서 방문 배열을 사용하지 않고, 두 좌표를 pair로 저장하는 벡터에 저장했다.

 

로봇이 움직일 수 있는 경우는 크게 3개로 나뉜다.

1) 회전하지 않고 상하좌우로 이동하는 경우

2) 좌표1을 기준으로 회전하는 경우

3) 좌표2를 기준으로 회전하는 경우

 

좌표1, 좌표2 둘 중 하나라도 벽과 겹쳐서는 안되고, 회전하는 방향에 있는 대각선 블록에도 벽이 있어서는 안된다는 사실을 인지하고 모든 경우를 반영하면 된다.

그리고 좌표1, 좌표2 둘 중 하나라도 (N, N)에 도달하면 BFS 깊이를 반환하도록 한다.

 

 

소스 코드

#include <vector>
#include <queue>
using namespace std;

int x[4]={1, -1, 0, 0};
int y[4]={0, 0, -1, 1};

struct point {
    int x;
    int y;
};

struct robot {
    point p1;
    point p2;
    int depth;
};

vector<pair<point, point> > v; // 방문 케이스 저장

int visited(point p1, point p2){
    for(int i=0;i<v.size();i++){
        if(v[i].first.x==p1.x&&v[i].first.y==p1.y&&
          v[i].second.x==p2.x&&v[i].second.y==p2.y) return 1;
    }
    return 0;
}


int solution(vector<vector<int>> board) {
    int nx1, ny1, nx2, ny2;
    queue<robot> q;
    int bsize=board.size();
    robot r = {{0, 0},{0, 1}, 0};
    q.push(r);
    v.push_back({r.p1, r.p2});            
    while(!q.empty()){
        robot fr = q.front(); q.pop();
        
        // 목적지에 도착했을 때 깊이 반환
        if((fr.p1.x==bsize-1&&fr.p1.y==bsize-1)||
          (fr.p2.x==bsize-1&&fr.p2.y==bsize-1)) return fr.depth;
          
        // 상하좌우 이동
        for(int k=0;k<4;k++){
            nx1=fr.p1.x+x[k]; ny1=fr.p1.y+y[k];
            nx2=fr.p2.x+x[k]; ny2=fr.p2.y+y[k];
            if(nx1<0||nx1>=bsize||ny1<0||ny1>=bsize) continue; //p1 이탈 검사
            if(nx2<0||nx2>=bsize||ny2<0||ny2>=bsize) continue; //p2 이탈 검사
            if(!visited({nx1, ny1}, {nx2, ny2})&&
               !board[nx1][ny1]&&!board[nx2][ny2]){ // 상하좌우 이동
                q.push({{nx1, ny1}, {nx2, ny2}, fr.depth+1});
                v.push_back({{nx1, ny1}, {nx2, ny2}});
            }
        }
        
        // p1 기준 회전
        if(fr.p1.x==fr.p2.x-1){ //p1 아래에 p2
            if(fr.p2.y+1<bsize&&!board[fr.p2.x][fr.p2.y+1]&&!board[fr.p1.x][fr.p1.y+1]&&!visited(fr.p1,{fr.p1.x, fr.p1.y+1})){
                q.push({fr.p1, {fr.p1.x, fr.p1.y+1}, fr.depth+1});
                v.push_back({fr.p1, {fr.p1.x, fr.p1.y+1}});
            }
            if(fr.p2.y-1>=0&&!board[fr.p2.x][fr.p2.y-1]&&!board[fr.p1.x][fr.p1.y-1]&&!visited(fr.p1,{fr.p1.x, fr.p1.y-1})){
                q.push({fr.p1, {fr.p1.x, fr.p1.y-1}, fr.depth+1});
                v.push_back({fr.p1, {fr.p1.x, fr.p1.y-1}});
            }
        }
        else if(fr.p1.x==fr.p2.x+1){ //p1 위에 p2
            if(fr.p2.y+1<bsize&&!board[fr.p2.x][fr.p2.y+1]&&!board[fr.p1.x][fr.p1.y+1]&&!visited(fr.p1,{fr.p1.x, fr.p1.y+1})){
                q.push({fr.p1, {fr.p1.x, fr.p1.y+1}, fr.depth+1});
                v.push_back({fr.p1, {fr.p1.x, fr.p1.y+1}});
            }
            if(fr.p2.y-1>=0&&!board[fr.p2.x][fr.p2.y-1]&&!board[fr.p1.x][fr.p1.y-1]&&!visited(fr.p1,{fr.p1.x, fr.p1.y-1})){
                q.push({fr.p1, {fr.p1.x, fr.p1.y-1}, fr.depth+1});
                v.push_back({fr.p1, {fr.p1.x, fr.p1.y-1}});
            }
        }
        else if(fr.p1.y==fr.p2.y+1){ // p1 왼쪽에 p2
            if(fr.p2.x-1>=0&&!board[fr.p2.x-1][fr.p2.y]&&!board[fr.p1.x-1][fr.p1.y]&&!visited(fr.p1,{fr.p1.x-1, fr.p1.y})){
                q.push({fr.p1, {fr.p1.x-1, fr.p1.y}, fr.depth+1});
                v.push_back({fr.p1, {fr.p1.x-1, fr.p1.y}});
            }
            if(fr.p2.x+1<bsize&&!board[fr.p2.x+1][fr.p2.y]&&!board[fr.p1.x+1][fr.p1.y]&&!visited(fr.p1,{fr.p1.x+1, fr.p1.y})){
                q.push({fr.p1, {fr.p1.x+1, fr.p1.y}, fr.depth+1});
                v.push_back({fr.p1, {fr.p1.x+1, fr.p1.y}});
            }
        }
        else if(fr.p1.y==fr.p2.y-1){ // p1 오른쪽에 p2
            if(fr.p2.x-1>=0&&!board[fr.p2.x-1][fr.p2.y]&&!board[fr.p1.x-1][fr.p1.y]&&!visited(fr.p1,{fr.p1.x-1, fr.p1.y})){
                q.push({fr.p1, {fr.p1.x-1, fr.p1.y}, fr.depth+1});
                v.push_back({fr.p1, {fr.p1.x-1, fr.p1.y}});
            }
            if(fr.p2.x+1<bsize&&!board[fr.p2.x+1][fr.p2.y]&&!board[fr.p1.x+1][fr.p1.y]&&!visited(fr.p1,{fr.p1.x+1, fr.p1.y})){
                q.push({fr.p1, {fr.p1.x+1, fr.p1.y}, fr.depth+1});
                v.push_back({fr.p1, {fr.p1.x+1, fr.p1.y}});
            }
        }

        // p2 기준 회전
        if(fr.p2.x==fr.p1.x-1){ //p2 아래에 p1
            if(fr.p1.y+1<bsize&&!board[fr.p1.x][fr.p1.y+1]&&!board[fr.p2.x][fr.p2.y+1]&&!visited(fr.p2,{fr.p2.x, fr.p2.y+1})){
                q.push({fr.p2, {fr.p2.x, fr.p2.y+1}, fr.depth+1});
                v.push_back({fr.p2, {fr.p2.x, fr.p2.y+1}});
            }
            if(fr.p1.y-1>=0&&!board[fr.p1.x][fr.p1.y-1]&&!board[fr.p2.x][fr.p2.y-1]&&!visited(fr.p2,{fr.p2.x, fr.p2.y-1})){
                q.push({fr.p2, {fr.p2.x, fr.p2.y-1}, fr.depth+1});
                v.push_back({fr.p2, {fr.p2.x, fr.p2.y-1}});
            }
        }
        else if(fr.p2.x==fr.p1.x+1){ //p2 위에 p1
            if(fr.p1.y+1<bsize&&!board[fr.p1.x][fr.p1.y+1]&&!board[fr.p2.x][fr.p2.y+1]&&!visited(fr.p2,{fr.p2.x, fr.p2.y+1})){
                q.push({fr.p2, {fr.p2.x, fr.p2.y+1}, fr.depth+1});
                v.push_back({fr.p2, {fr.p2.x, fr.p2.y+1}});
            }
            if(fr.p1.y-1>=0&&!board[fr.p1.x][fr.p1.y-1]&&!board[fr.p2.x][fr.p2.y-1]&&!visited(fr.p2,{fr.p2.x, fr.p2.y-1})){
                q.push({fr.p2, {fr.p2.x, fr.p2.y-1}, fr.depth+1});
                v.push_back({fr.p2, {fr.p2.x, fr.p2.y-1}});
            }
        }
        else if(fr.p2.y==fr.p1.y+1){ //p2 왼쪽에 p1
            if(fr.p1.x-1>=0&&!board[fr.p1.x-1][fr.p1.y]&&!board[fr.p2.x-1][fr.p2.y]&&!visited(fr.p2,{fr.p2.x-1, fr.p2.y})){
                q.push({fr.p2, {fr.p2.x-1, fr.p2.y}, fr.depth+1});
                v.push_back({fr.p2, {fr.p2.x-1, fr.p2.y}});
            }
           if(fr.p1.x+1<bsize&&!board[fr.p1.x+1][fr.p1.y]&&!board[fr.p2.x+1][fr.p2.y]&&!visited(fr.p2,{fr.p2.x+1, fr.p2.y})){
                q.push({fr.p2, {fr.p2.x+1, fr.p2.y}, fr.depth+1});
                v.push_back({fr.p2, {fr.p2.x+1, fr.p2.y}});
            }
        }
        else if(fr.p2.y==fr.p1.y-1){ //p2 오른쪽에 p1
            if(fr.p1.x-1>=0&&!board[fr.p1.x-1][fr.p1.y]&&!board[fr.p2.x-1][fr.p2.y]&&!visited(fr.p2,{fr.p2.x-1, fr.p2.y})){
                q.push({fr.p2, {fr.p2.x-1, fr.p2.y}, fr.depth+1});
                v.push_back({fr.p2, {fr.p2.x-1, fr.p2.y}});
            }
            if(fr.p1.x+1<bsize&&!board[fr.p1.x+1][fr.p1.y]&&!board[fr.p2.x+1][fr.p2.y]&&!visited(fr.p2,{fr.p2.x+1, fr.p2.y})){
                q.push({fr.p2, {fr.p2.x+1, fr.p2.y}, fr.depth+1});
                v.push_back({fr.p2, {fr.p2.x+1, fr.p2.y}});
            }
        }
    }  
    return 0;
}

 

테스트케이스 14개 모두 정답