문제 설명: 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다. 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다. "0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 반환하는 함수를 작성
입력
board의 한 변의 길이는 5 이상 100 이하
로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어짐
로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어짐
출력: 최소 시간
풀이
로봇을 상하좌우로 이동하거나 회전하는 경우 1초가 지나기 때문에 로봇의 위치를 노드로 저장해서 BFS로 구현
로봇의 두 좌표 중 하나라도 (N, N)에 도달하면 그 때 걸린 시간이 최소 시간
로봇의 위치를 어떻게 나타낼 것인가? 두 좌표 중 1개(x,y)와 그 좌표에서 다음 좌표를 가리키는 방향(상/하/좌/우 총 4가지)
두 좌표를 저장하는 것보다 회전/이동이 쉽고 방문 체크나 벽 체크하기 용이함
로봇의 좌표를 c1과 c2라고 할 때 방향(dir)에 따라 좌표는 아래와 같음
좌표의 변화? (dir 은 d배열의 인덱스)
움직이는 경우 => c1 에만 변화를 주고 dir은 그대로
회전하는 경우 => c1, c2 각각에 대해 다음과 같이 2가지 종류로 회전
dir=0,2 이면 dir=1,3 으로 호출
dir=1,3 이면 dir=0,2 으로 호출
회전한 후의 좌표를 (ny,nx)라 할 때 돌리는 방향에 벽이 없어야 함
dir=0,2
c1이 축이면 (ny, c2.X) 와 회전 후 좌표 모두 벽이 아니고 범위 안에 있어야 함
c2가 축이면 (ny, c1.X) 와 회전 후 좌표 모두 벽이 아니고 범위 안에 있어야 함
dir=1,3
c1이 축이면 (c2.Y, nx) 와 회전 후 좌표 모두 벽이 아니고 범위 안에 있어야 함
c2가 축이면 (c1.Y, nx) 와 회전 후 좌표 모두 벽이 아니고 범위 안에 있어야 함
정답 코드
#include <string>
#include <vector>
#include <queue>
#include <cstring>
#define Y first
#define X second
using namespace std;
typedef pair<int,int> pii;
const int d[5] = {0, -1, 0, 1, 0};
vector<vector<int>> B;
int N;
bool isInRange(pii c) {
if (c.Y < 0 or c.Y >= N or c.X < 0 or c.X >= N) return false;
return !B[c.Y][c.X];
}
int bfs() {
int ret = 0;
bool visited[100][100][4];
memset(visited, 0, sizeof(visited));
queue<pair<int, pii>> q; // (dir, (y,x))
q.push({2, {0,0}});
visited[0][0][2] = true;
while (!q.empty()) {
int sz = q.size();
while (sz--) { // depth 계산을 정확하게 하기 위해 딱 존재하는 노드만큼만 수행
int dir = q.front().first;
pii c1 = q.front().second;
pii c2 = {c1.Y + d[dir], c1.X + d[dir+1]};
q.pop();
if ((c1.Y == N-1 and c1.X == N-1) or (c2.Y == N-1 and c2.X == N-1))
return ret;
// 상하좌우 이동: (y,x)만 변화를 주고 dir은 그대로 유지
for (int i = 0; i < 4; i++) {
pii nc1 = {c1.Y + d[i], c1.X + d[i+1]};
pii nc2 = {nc1.Y + d[dir], nc1.X + d[dir+1]};
if (isInRange(nc1) and isInRange(nc2) and !visited[nc1.Y][nc1.X][dir]) {
q.push({dir, nc1});
visited[nc1.Y][nc1.X][dir] = true;
}
}
// 회전: dir에 따라 회전할 방향과 좌표 검사를 함
int newDir[2] = {(dir&1) ? 0 : 1, (dir&1) ? 2 : 3};
for (int i = 0; i < 2; i++) {
int rd = newDir[i];
pii nc2 = {c1.Y + d[rd], c1.X + d[rd+1]};
// c1 을 축으로 회전
if (isInRange(nc2)) {
if (((dir & 1) and isInRange({c2.Y, nc2.X})) or
(!(dir & 1) and isInRange({nc2.Y, c2.X}))) {
if (!visited[c1.Y][c1.X][rd]) {
q.push({rd, c1});
visited[c1.Y][c1.X][rd] = true;
}
}
}
// c2 를 축으로 회전
pii nc1 = {c2.Y + d[rd], c2.X + d[rd+1]};
if (isInRange(nc1)) {
if (((dir & 1) and isInRange({c1.Y, nc1.X})) or
(!(dir & 1) and isInRange({nc1.Y, c1.X}))) {
if (!visited[c2.Y][c2.X][rd]) {
q.push({rd, c2});
visited[c2.Y][c2.X][rd] = true;
}
}
}
}
}
ret++;
}
return ret;
}
int solution(vector<vector<int>> board) {
N = board.size();
B = board;
return bfs();
}
