문제
문제 설명
로봇개발자 무지는 한 달 앞으로 다가온 카카오배 로봇경진대회에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 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 |
풀이
뚝딱 풀고 다른 공부 하려고 시작한 문제였는데 하루종일 붙잡고 있었다. 완전 짱난다.
bfs로 혼자 코드를 짰는데, 우하단쪽으로만 움직이도록 경우의 수를 자체적으로 제한하고 코드를 짰더니 답이 절대 나오지 않았다. 머리 싸매다가 결국 검색했더니, 상하좌우 + 위아래 회전 모두 고려해야 한다고 하더라..그래서 최단거리가 필요한 것 맞지만, 목적지 방향으로만 움직여야 최단거리가 된다는 것은 아니었다. 내 맘대로 범위를 좁히지 말고 좀 더 깊게 생각할 필요가 있는 것 같다.
그리고 count를 세는 방법도 잘못 정의했었고, visited도 방향에 따라 정의하지 않고 퉁쳐서 했었다. 결국 다른 분의 코드를 참고해서 하나하나 이해하고 다른 코드랑 비교해서 이해하기 쉬운 방향으로 살짝 건드는 정도만 하고 마무리했다. 흑흑흑.
아무튼 문제만 읽었을 때는 이렇게 조건을 정의하는 게 어려운 문제인지 몰랐다.. BFS를 떠올리고 코드의 전체적인 흐름 틀을 잡았다는 것에 의의를 두자...
코드
import java.util.LinkedList;
import java.util.Queue;
class Solution {
private static final int HORIZONTAL = 0;
private static final int VERTICAL = 1;
private static int[][] map;
private static int size;
private static boolean[][][] visited;
private static Queue<Robot> queue = new LinkedList<>();
private static int[] dx = {-1, 1, 0, 0};
private static int[] dy = {0, 0, -1, 1};
public int solution(int[][] board) {
map = board;
size = board.length;
visited = new boolean[2][size][size];
return bfs();
}
private int bfs() {
int count = 0;
queue.offer(new Robot(new Point(0, 0), new Point(0, 1), true));
queue.offer(null);
visited[HORIZONTAL][0][0] = true;
visited[HORIZONTAL][0][1] = true;
while (!queue.isEmpty()) {
Robot current = queue.poll();
if (current == null) {
count++;
if (!queue.isEmpty()) queue.offer(null);
continue;
}
if ((current.p1.x == size - 1 && current.p1.y == size - 1) || (current.p2.x == size - 1 && current.p2.y == size - 1))
break;
checkAdjacent(current);
}
return count;
}
private void checkAdjacent(Robot current) {
if (current.isHorizontal) {
checkFourDirections(current, HORIZONTAL);
checkRotations(current, HORIZONTAL);
} else {
checkFourDirections(current, VERTICAL);
checkRotations(current, VERTICAL);
}
}
private void checkFourDirections(Robot current, int direction) {
for (int i = 0; i < 4; i++) {
Robot next;
if (direction == HORIZONTAL)
next = new Robot(new Point(current.p1.x + dx[i], current.p1.y + dy[i]), new Point(current.p2.x + dx[i], current.p2.y + dy[i]), true);
else
next = new Robot(new Point(current.p1.x + dx[i], current.p1.y + dy[i]), new Point(current.p2.x + dx[i], current.p2.y + dy[i]), false);
if (isAvailable(next.p1) && isAvailable(next.p2)) {
if (!visited[direction][next.p1.x][next.p1.y] || !visited[direction][next.p2.x][next.p2.y]) {
visited[direction][next.p1.x][next.p1.y] = true;
visited[direction][next.p2.x][next.p2.y] = true;
queue.offer(next);
}
}
}
}
private void checkRotations(Robot current, int direction) {
Point np1, np2;
for (int i = -1; i <= 1; i += 2) {
if (direction == HORIZONTAL) {
np1 = new Point(current.p1.x + i, current.p1.y);
np2 = new Point(current.p2.x + i, current.p2.y);
} else {
np1 = new Point(current.p1.x, current.p1.y + i);
np2 = new Point(current.p2.x, current.p2.y + i);
}
checkOneRotation(np1, np2, current, direction);
}
}
private void checkOneRotation(Point np1, Point np2, Robot current, int direction) {
if (isAvailable(np1) && isAvailable(np2)) {
if (isRotatable(np1, current.p1) && !visited[Math.abs(direction - 1)][np1.x][np1.y] || !visited[Math.abs(direction - 1)][current.p1.x][current.p1.y]) {
visited[Math.abs(direction - 1)][np1.x][np1.y] = true;
visited[Math.abs(direction - 1)][current.p1.x][current.p1.y] = true;
if (direction == HORIZONTAL)
queue.offer(new Robot(np1, current.p1, false));
else
queue.offer(new Robot(np1, current.p1, true));
}
if (isRotatable(np2, current.p2) && !visited[Math.abs(direction - 1)][np2.x][np2.y] || !visited[Math.abs(direction - 1)][current.p2.x][current.p2.y]) {
visited[Math.abs(direction - 1)][np2.x][np2.y] = true;
visited[Math.abs(direction - 1)][current.p2.x][current.p2.y] = true;
if (direction == HORIZONTAL)
queue.offer(new Robot(np2, current.p2, false));
else
queue.offer(new Robot(np2, current.p2, true));
}
}
}
private boolean isAvailable(Point point) {
return point.x >= 0 && point.x < size && point.y >= 0 && point.y < size && map[point.x][point.y] == 0;
}
private boolean isRotatable(Point p1, Point p2) {
return isAvailable(p1) && isAvailable(p2);
}
}
class Robot {
Point p1;
Point p2;
boolean isHorizontal;
public Robot(Point p1, Point p2, boolean isHorizontal) {
this.p1 = p1;
this.p2 = p2;
this.isHorizontal = isHorizontal;
}
}
class Point {
int x;
int y;
public Point(int x, int y) {
this.x = x;
this.y = y;
}
}