(2020 KAKAO BLIND) 블록 이동하기
문제 설명
로봇개발자 “무지”는 한 달 앞으로 다가온 “카카오배 로봇경진대회”에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
문제 풀이
그동안은 pair, tuple 등의 자료형으로 어떻게든 문제가 풀렸기 때문에 pair나 tuple로 처리가 불가능한 자료구조가 필요한 상황이 오자 패닉이 왔다. 결국 아이디어는 있지만 그를 구현할 방법을 찾지 못해 해답을 참고하게 됬는데 해결방법은 너무나 간단했다. struct나 class로 내가 필요한 자료형을 스스로 만들면 되는 것 뿐이었다. 문제 자체는 최단경로를 찾는 문제로 bfs를 사용하여 모든 경우의 수를 테스트해보면 정답이 나온다. 이 때 주의할 점은 로봇이 두 칸을 차지한다는 점이다.
bfs의 구조 상 visited 등의 배열을 사용하여 이미 방문한 지점은 다시 방문하지 않는 것으로 무한한 루프를 방지하는데, 이 문제의 경우 한 칸의 visited가 가로 로봇의 첫번째 칸이 방문, 두번째 칸이 방문, 세로 로봇의 첫번째(위쪽)칸이 방문, 두번째(아래쪽)칸이 방문 총 4개를 따로 체크해야 한다는 점을 유의해야한다. 또한 로봇의 회전 또한 움직임 중 하나로 들어가는데 회전을 위해선 회전하는 쪽의 칸 두 개가 비어있어야 한다. 첫번째 사진과 같이 가로로 된 로봇이 세로로 회전하기 위해서는 아래쪽 칸 두개가 비어있어야 하는 것이다. 따라서 우리가 bfs의 매 루프마다 체크해줘야 하는 것은 (가로일때) 로봇의 좌우 이동, 그리고 로봇의 위 칸이나 아래칸 두개가 비었는지를 확인하고 상하 이동 및 회전(축을 어느쪽으로 잡냐에 따라 두 경우) 합쳐서 8개의 체크를 하게 된다. 천천히 생각해보면 어렵지 않은 문제였지만 아직 공부가 부족하여 상황 대응력이 떨어지는 것을 많이 느낀 문제였다.
코드 풀이
#include <string>
#include <vector>
#include <queue>
using namespace std;
struct part {
int a; int b; int dir;
};
struct robot {
part part1; part part2;
int count=0;
};
int solution(vector<vector<int>> board) {
int answer = 100000;
bool visit[100][100][4] = {false};
queue<robot> q;
robot tmp={ {0,0,0}, {0,1,1}, 0};
visit[0][0][0]=true; visit[0][1][1]=true;
q.push(tmp);
while(!q.empty()) {
robot r=q.front(); q.pop();
part p1=r.part1; part p2=r.part2;
if(p1.a==board.size()-1 && p1.b==board.size()-1) {
if(answer>r.count) answer=r.count;
break;
}
if(p2.a==board.size()-1 && p2.b==board.size()-1) {
if(answer>r.count) answer=r.count;
break;
}
int count=r.count+1;
if(p1.dir==0) {
if(p2.b+1<board.size() && board[p2.a][p2.b+1]!=1) {
robot tmp={ {p1.a, p1.b+1, 0}, {p2.a, p2.b+1, 1}, count};
if(visit[p1.a][p1.b+1][0]==false) {
q.push(tmp);
visit[p1.a][p1.b+1][0]=true;
visit[p2.a][p2.b+1][1]=true; }
}
if(p1.b-1>=0 && board[p1.a][p1.b-1]!=1) {
robot tmp={ {p1.a, p1.b-1, 0}, {p2.a, p2.b-1, 1}, count};
if(visit[p1.a][p1.b-1][0]==false) {
q.push(tmp);
visit[p1.a][p1.b-1][0];
visit[p2.a][p2.b-1][0];
}
}
if(p1.a-1>=0 && board[p1.a-1][p1.b]!=1 && board[p2.a-1][p2.b]!=1) {
robot tmp={ {p1.a-1, p1.b, 0}, {p2.a-1, p2.b, 1}, count};
if(visit[p1.a-1][p1.b][0]==false) {
q.push(tmp);
visit[p1.a-1][p1.b][0];
visit[p2.a-1][p2.b][0];
}
tmp={ {p1.a-1, p1.b, 2}, {p1.a, p1.b, 3}, count};
if(visit[p1.a-1][p1.b][2]==false) {
q.push(tmp);
visit[p1.a-1][p1.b][2]=true;
visit[p1.a][p1.b][3]=true;
}
tmp={ {p2.a-1,p2.b, 2}, {p2.a, p2.b, 3}, count};
if(visit[p2.a-1][p2.b][2]==false) {
q.push(tmp);
visit[p2.a-1][p2.b][2]=true;
visit[p2.a][p2.b][3]=true;
}
}
if(p1.a+1<board.size() && board[p1.a+1][p1.b]!=1 && board[p2.a+1][p2.b]!=1) {
robot tmp={ {p1.a+1, p1.b, 0}, {p2.a+1, p2.b, 1}, count};
if(visit[p1.a+1][p1.b][0]==false) {
q.push(tmp);
visit[p1.a+1][p1.b][0];
visit[p2.a+1][p2.b][0];
}
tmp={ {p1.a, p1.b, 2}, {p1.a+1, p1.b, 3}, count};
if(visit[p1.a][p1.b][2]==false) {
q.push(tmp);
visit[p1.a][p1.b][2]=true;
visit[p1.a+1][p1.b][3]=true;
}
tmp={ {p2.a,p2.b, 2}, {p2.a+1, p2.b, 3}, count};
if(visit[p2.a][p2.b][2]==false) {
q.push(tmp);
visit[p2.a][p2.b][2]=true;
visit[p2.a+1][p2.b][3]=true;
}
}
}
else if(p1.dir==2) {
if(p2.a+1<board.size() && board[p2.a+1][p2.b]!=1) {
robot tmp={ {p1.a+1, p1.b, 2}, {p2.a+1, p2.b, 3}, count};
if(visit[p1.a+1][p1.b][2]==false) {
q.push(tmp);
visit[p1.a+1][p1.b][2]=true;
visit[p2.a+1][p2.b][3]=true; }
}
if(p1.a-1>=0 && board[p1.a-1][p1.b]!=1) {
robot tmp={ {p1.a-1, p1.b, 2}, {p2.a-1, p2.b, 3}, count};
if(visit[p1.a-1][p1.b][2]==false) {
q.push(tmp);
visit[p1.a-1][p1.b][2];
visit[p2.a-1][p2.b][3];
}
}
if(p1.b-1>=0 && board[p1.a][p1.b-1]!=1 && board[p2.a][p2.b-1]!=1) {
robot tmp={ {p1.a, p1.b-1, 2}, {p2.a, p2.b-1, 3}, count};
if(visit[p1.a][p1.b-1][2]==false) {
q.push(tmp);
visit[p1.a][p1.b-1][2];
visit[p2.a][p2.b-1][3];
}
tmp={ {p1.a, p1.b-1, 0}, {p1.a, p1.b, 1}, count};
if(visit[p1.a][p1.b-1][0]==false) {
q.push(tmp);
visit[p1.a][p1.b-1][0]=true;
visit[p1.a][p1.b][1]=true;
}
tmp={ {p2.a,p2.b-1, 0}, {p2.a, p2.b, 1}, count};
if(visit[p2.a][p2.b-1][0]==false) {
q.push(tmp);
visit[p2.a][p2.b-1][0]=true;
visit[p2.a][p2.b][1]=true;
}
}
if(p1.b+1<board.size() && board[p1.a][p1.b+1]!=1 && board[p2.a][p2.b+1]!=1) {
robot tmp={ {p1.a, p1.b+1, 2}, {p2.a, p2.b+1, 3}, count};
if(visit[p1.a][p1.b+1][2]==false) {
q.push(tmp);
visit[p1.a][p1.b+1][2];
visit[p2.a][p2.b+1][3];
}
tmp={ {p1.a, p1.b, 0}, {p1.a, p1.b+1, 1}, count};
if(visit[p1.a][p1.b][0]==false) {
q.push(tmp);
visit[p1.a][p1.b][0]=true;
visit[p1.a][p1.b+1][1]=true;
}
tmp={ {p2.a,p2.b, 0}, {p2.a, p2.b+1, 1}, count};
if(visit[p2.a][p2.b][0]==false) {
q.push(tmp);
visit[p2.a][p2.b][0]=true;
visit[p2.a][p2.b+1][1]=true;
}
}
}
}
return answer;
}