[C++] 2020 카카오 블라인드 블록이동하기

문제 설명

---

로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 무지는 0과 1로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 0은 빈칸을 1은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

0과 1로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한사항

• board의 한 변의 길이는 5 이상 100 이하입니다.
• board의 원소는 0 또는 1입니다.
• 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
• 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

---

입출력 예

boardresult

[[0, 0, 0, 1, 1],[0, 0, 0, 1, 0],[0, 1, 0, 1, 1],[1, 1, 0, 0, 1],[0, 0, 0, 0, 0]]

7

입출력 예에 대한 설명

문제에 주어진 예시와 같습니다.
로봇이 오른쪽으로 한 칸 이동 후, (1, 3) 칸을 축으로 반시계 방향으로 90도 회전합니다. 다시, 아래쪽으로 3칸 이동하면 로봇은 (4, 3), (5, 3) 두 칸을 차지하게 됩니다. 이제 (5, 3)을 축으로 시계 방향으로 90도 회전 후, 오른쪽으로 한 칸 이동하면 (N, N)에 도착합니다. 따라서 목적지에 도달하기까지 최소 7초가 걸립니다.

 

 

접근 방법

---

 출발 지점으로 부터 도착지까지 최소 이동횟수를 구하는 문제로 BFS를 사용하여 구할 수 있습니다. 이 때 한 턴에서 이동하는 방법은 상하좌우 4가지,  회전하는 경우 4가지로 총 8가지의 방법이 있습니다.

 

1. BFS를 사용하기 위해 방문여부를 체크해야 하는데 이 때 visited[x][y][x][y]의 4차원 배열로 확인을 하였고, 로봇은 2개의 좌표로 이루어져 있기 때문에 visited[x1][y1][x2][y2], visited[x2][y2][x1][y1]을 같은 경우의 수로 생각해야 합니다. 

 

2. 로봇이 상하좌우로 이동할 때에는 이동하려는 곳에 벽이 있는지 범위를 벗어나지 않았는지에 대해 확인을 하면 어렵지 않게 구현을 할 수 있습니다.

 

3. 로봇이 회전을 하는 경우에 대해서는 조금 생각을 해야 하는데, 2번에서의 조건을 만족하면서 회전 동작을 진행 할 때 방해하는 벽이 있는지 먼저 확인을 해야합니다.

 

저와 같은 경우는 아래 그림과 같이 구현을 하였습니다.

 

만약 아래의 그림과 같이 로봇을 회전 시키고 싶다면 로봇아래 두칸(검은 선이 그려진 부분)에 벽이 있는지 확인을 합니다.

확인을 한 이후에 벽이 없다면 회전을 시키면 됩니다. 자세한 내용은 아래 소스코드에 주석으로 달아 놓았습니다.

 //dir이 4~7일 때는 회전에 대한 동작이며 그에 해당하는 경우에 대한 논리
 //coord nextDir[4] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
 //tmp는 robot의 상태로 초기화 했으며 회전한 상태를 return하기 위한 변수
 //state가 true면 로봇이 가로로 놓여있는 상태, false면 새로로 놓여있는 상태
 bool state = (tmp[0].x == tmp[1].x) ? true:false; 
 	int dirtmp = dir - 4; //dir의 값을 미리 저장

	if(state) dir = (dir < 6) ? 0 : 2;
	else dir = (dir < 6) ? 1 : 3;
	
    //로봇은 좌표 2칸을 차지하기 때문에 robot.size()인 2개의 좌표를 모두 검사해야함
	for(int i=0;i<robot.size();i++){
        tmp[i].x = robot[i].x + nextDir[dir].x;
        tmp[i].y = robot[i].y + nextDir[dir].y;
        //범위를 벗어나거나 로봇이 회전하는데 방해하는 벽이 있다면
        if(!inRange(tmp[i]) || map[tmp[i].x][tmp[i].y]) 
        	return robot;    
    }

//회전을 할 수 있다면 방향에 맞게 회전
if(dirtmp == 0 || dirtmp == 2) tmp[0] = robot[1];
else tmp[1] = robot[0];

 

 

 

소스 코드

---

#include <string>
#include <queue>
#include <vector>

using namespace std;

typedef struct coord{
    int x, y;
};

coord nextDir[4] = {{1,0}, {0,1}, {-1,0}, {0,-1}};
bool visited[101][101][101][101];
vector<vector<int>> map;
int N;

bool inRange(coord &xy){
    return (0 <= xy.x && xy.x < N && 0 <= xy.y && xy.y < N);
}

bool isVisited(vector<coord> &robot){
    return (visited[robot[0].x][robot[0].y][robot[1].x][robot[1].y] || visited[robot[1].x][robot[1].y][robot[0].x][robot[0].y]);
}

bool isDest(vector<coord> &robot){
    for(int i=0;i<robot.size();i++)
        if(robot[i].x == N - 1 && robot[i].y == N - 1)
            return true;
    return false;
}

vector<coord> nextState(vector<coord> robot, int dir){
    
    vector<coord> tmp = robot;
    
    if(dir < 4){
        for(int i=0;i<robot.size();i++){
            tmp[i].x = robot[i].x + nextDir[dir].x;
            tmp[i].y = robot[i].y + nextDir[dir].y;
            if(!inRange(tmp[i]) || map[tmp[i].x][tmp[i].y]) //범위를 벗어나거나 벽이라면
                return robot;
        }
    }
    else{
        //state가 true면 가로로 놓여있는 상태, false면 새로로 놓여있는 상태
        bool state = (tmp[0].x == tmp[1].x) ? true:false; 
        int dirtmp = dir - 4;
        
        if(state) dir = (dir < 6) ? 0 : 2;
        else dir = (dir < 6) ? 1 : 3;
        
        for(int i=0;i<robot.size();i++){
            tmp[i].x = robot[i].x + nextDir[dir].x;
            tmp[i].y = robot[i].y + nextDir[dir].y;
            if(!inRange(tmp[i]) || map[tmp[i].x][tmp[i].y]) //범위를 벗어나거나 벽이라면
                return robot;    
        }
        
        if(dirtmp == 0 || dirtmp == 2) tmp[0] = robot[1];
        else tmp[1] = robot[0];
    }
    return tmp;
}

int BFS(){
    
    vector<coord> robot = {{0,0},{0,1}};
    queue<pair<vector<coord>, int>> q; //로봇과 이동시간
    
    q.push({robot, 0});
    visited[0][0][0][1] = true;
    visited[0][1][0][0] = true;
    
    while(!q.empty()){
        
        vector<coord> now = q.front().first;
        int cnt = q.front().second;
        q.pop();
        
        for(int i=0;i<8;i++){
        
            vector<coord> next = nextState(now, i);
            
            if(!isVisited(next)){
                if(isDest(next))
                    return cnt + 1;
                q.push({next, cnt + 1});
                visited[next[0].x][next[0].y][next[1].x][next[1].y] = true;
                visited[next[1].x][next[1].y][next[0].x][next[0].y] = true;
            }
        }
    }
    return 0;
}

int solution(vector<vector<int>> board) {
    
    N = board.size();
    map = board;
    int answer = BFS();
    return answer;
}