문제 설명
https://programmers.co.kr/learn/courses/30/lessons/60063
코딩테스트 연습 - 블록 이동하기
[[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
programmers.co.kr
로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
입출력 예
| board | result |
| [[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 형태로 길을 찾아나간다. 하지만 이 문제의 특별한 점은 바로 한 번에 2개 위치를 차지하는 드론이라는 점과, 해당 드론이 회전할 수 있다는 점이었다. 그러다 보니 기존 위치 정보를 저장할 때도 2개의 좌표를 동시에 하나에 담아서 큐에 넣어야 하고, 해당 위치를 이미 중복해서 다녀왔는지를 확인하기 위한 자료구조 또한 다르게 만들어야 했다.
이를 해결하기 위해 우선 드론의 위치 정보를 모두 담을 수 있는 구조체를 만들어, 드론의 좌표 2개와 해당 드론이 가로로 있는 상태인지 세로로 있는 상태인지, 추가적으로 해당 위치에 있을 때의 시간을 저장하고, 이를 큐에 넣어 BFS를 사용하기 위한 자료 구조를 구현한다. 이후 해당 위치를 이미 다녀왔는지를 확인하기 위해 unordered_set을 활용하여 현재 드론의 위치 좌표 2개의 행, 열 좌표를 하나의 문자열 형태로 키 값으로 자료구조를 만들어, 해당 자료구조에 키 값을 바탕으로 중복을 판단한다.
이러한 자료구조를 바탕으로, 우선적으로 시작위치 정보를 담은 구조체를 만들어 큐에 담고 BFS를 수행한다. 드론의 기본적인 상하좌우 이동과, 드론의 회전을 모두 각각의 구조체로 만들고 해당 위치가 적절한 지를 판단하는 함수를 통해 최종적으로 적절한 경우 unordered_set에 해당 키 값을 넣고 큐에 해당 구조체를 넣는 것을 수행한다. 이러한 반복을 통해 목표 위치에 도달한 경우, 해당 구조체 속 시간을 반환하는 것으로 함수를 종료한다.
유의할 점
문제를 풀던 도중 계속 드론의 좌표를 생각하다 2차원 상의 좌표 표시 방식과 프로그래밍 언어에서의 행, 열 표시 방식이 반대인 걸 잊어 코드 상에서 계속 오류가 나왔다.
#include <string>
#include <vector>
#include <queue>
#include <unordered_set>
using namespace std;
struct infor {//드론의 정보 구조체
int x1, y1, x2, y2;
char state;
int time;
};
void check(vector<vector<int>>& board, infor next, unordered_set<string>& visited, int size, queue<infor> &q) {
int x1 = next.x1, y1 = next.y1, x2 = next.x2, y2 = next.y2;
//좌표가 비정상인 경우
if (x1 < 0 || x1 >= size || y1 < 0 || y1 >= size)
return;
if (x2 < 0 || x2 >= size || y2 < 0 || y2 >= size)
return;
//드론의 위치가 벽인 경우
if (board[x1][y1] == 1)
return;
if (board[x2][y2] == 1)
return;
//드론이 이미 온 적이 있는 경우
if (visited.find(to_string(x1) + '/' + to_string(y1) + '/' + to_string(x2) + '/' + to_string(y2)) != visited.end())
return;
//검증 완료 이후 처리
visited.insert(to_string(x1) + '/' + to_string(y1) + '/' + to_string(x2) + '/' + to_string(y2));
q.push(next);
return;
}
int solution(vector<vector<int>> board) {
int size = board.size();
queue<infor> q;
unordered_set<string> visited; //중복 확인
infor start;
vector<vector<int>> mov = { {-1,0}, {1,0}, {0,-1}, {0,1} }; //상하좌우
//시작 정보 생성 후 큐에 담는 과정
start.x1 = start.y1 = start.x2 = start.time = 0;
start.y2 = 1;
start.state = 'g';
visited.insert("0/0/0/1");
q.push(start);
//BFS 이용
while (!q.empty()) {
infor pos = q.front(); q.pop();//하나를 꺼내온다.
if ((pos.x1 == size - 1 && pos.y1 == size - 1) || (pos.x2 == size - 1 && pos.y2 == size - 1))
return pos.time;
infor next;
pos.time += 1;
for (int i = 0; i < 4; i++) {//기본적인 이동(상하좌우)
next = pos;
next.x1 += mov[i][0]; next.x2 += mov[i][0];
next.y1 += mov[i][1]; next.y2 += mov[i][1];
check(board, next, visited, size, q);
}
if (pos.state == 'g') {//현 드론이 가로인 경우의 회전
pos.state = 's';
if (pos.x1 < size - 1 && board[pos.x1 + 1][pos.y1] == 0 && board[pos.x2 + 1][pos.y2] == 0) {//아래쪽 회전이 가능
next = pos; //점1 기준 시계
next.y2 = next.y1;
next.x2 = next.x1 + 1;
check(board, next, visited, size, q);
next = pos; //점2 기준 반시계
next.y1 = next.y2;
next.x1 = next.x2 + 1;
check(board, next, visited, size, q);
}
if (pos.x1 > 0 && board[pos.x1 - 1][pos.y1] == 0 && board[pos.x2 - 1][pos.y2] == 0) {//위쪽 회전이 가능
next = pos; //점1 기준 반시계
next.y2 = next.y1;
next.x2 = next.x1 - 1;
check(board, next, visited, size, q);
next = pos; //점2 기준 시계
next.y1 = next.y2;
next.x1 = next.x2 - 1;
check(board, next, visited, size, q);
}
}
else {//현 드론이 세로인 경우의 회전
pos.state = 'g';
if (pos.y1 < size - 1 && board[pos.x1][pos.y1 + 1] == 0 && board[pos.x2][pos.y2 + 1] == 0) {//오른쪽 회전이 가능
next = pos; //점1 기준 반시계
next.y2 = next.y1 + 1;
next.x2 = next.x1;
check(board, next, visited, size, q);
next = pos; //점2 기준 시계
next.y1 = next.y2 + 1;;
next.x1 = next.x2;
check(board, next, visited, size, q);
}
if (pos.y1 > 0 && board[pos.x1][pos.y1 - 1] == 0 && board[pos.x2][pos.y2 - 1] == 0) {//왼쪽 회전이 가능
next = pos; //점1 기준 시계
next.y2 = next.y1 - 1;
next.x2 = next.x1;
check(board, next, visited, size, q);
next = pos; //점2 기준 반시계
next.y1 = next.y2 - 1;
next.x1 = next.x2;
check(board, next, visited, size, q);
}
}
}
return 0;
}결과
