문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/60063
문제 설명
링크 참조
제한사항
- board의 한 변의 길이는 5 이상 100 이하입니다.
- board의 원소는 0 또는 1입니다.
- 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
- 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.
알고리즘: BFS
이 문제는 로봇이 (N, N) 위치까지 이동하는 데 필요한 최소 시간을 구하는 문제다.
인접한 칸으로 이동하는 연산, 90도 회전하는 연산이 존재하는데 두 연산 모두 가중치가 1이다.
이 말은 즉 BFS를 이용해서 가장 먼저 목표에 도달한 노드가 정답이 되는 문제다.
방문 처리는 로봇이 두 개의 좌표를 차지하기 때문에 4차원 배열을 이용한다.
여기서 모든 좌표가 사용되는 건 아니다. 왜냐하면 인접한 두 개의 좌표이기 때문에 훨쒼 적을 것이다. (N이 100일 때 약 2만?)
사실 BFS 문제라는 것은 알기 쉽다. 하지만 이 문제의 진가는 회전 구현이다.
축을 기준으로 반시계 방향, 시계 방향 회전이 있으며 로봇이 가로일 때와 세로일 때 두 가지 경우로 또 나눠줘야 한다. 그리고 회전했을 때 left_wing과 right wing의 위치가 달라지기 때문에 이러한 경우도 고려할 사항이다.
풀이
소스 코드
import java.util.*;
class Node {
Point w1, w2;
int t;
Node() {
this.w1 = new Point(0, 0);
this.w2 = new Point(1, 0);
this.t = 0;
}
Node(Point wing1, Point wing2, int t) {
this.w1 = wing1;
this.w2 = wing2;
this.t = t;
}
}
class Point {
int x, y;
Point(int x, int y) {
this.x = x;
this.y = y;
}
}
class Solution {
static final int[] dx = {-1, 0, 1, 0};
static final int[] dy = {0, -1, 0, 1};
static boolean[][][][] visited; //[w1.y][w1.x][w2.y][w2.x]
static int[][] board;
static int N;
static int answer;
public int solution(int[][] Board) {
N = Board.length;
board = Board;
visited = new boolean[N][N][N][N];
BFS(new Node());
return answer;
}
static void BFS(Node start) {
Queue < Node > que = new LinkedList < > ();
que.add(start);
visited[start.w1.y][start.w1.x][start.w2.y][start.w2.x] = true;
while (que.size() != 0) {
Node n = que.poll();
if ((n.w1.y == N - 1 && n.w1.x == N - 1) || (n.w2.y == N - 1 && n.w2.x == N - 1)) {
answer = n.t;
return;
}
//이동
for (int i = 0; i < 4; i++) {
int w1_nx = n.w1.x + dx[i];
int w1_ny = n.w1.y + dy[i];
int w2_nx = n.w2.x + dx[i];
int w2_ny = n.w2.y + dy[i];
if (range_check(new Point(w1_nx, w1_ny)) && range_check(new Point(w2_nx, w2_ny))) {
if (!visited[w1_ny][w1_nx][w2_ny][w2_nx]) {
visited[w1_ny][w1_nx][w2_ny][w2_nx] = true;
que.add(new Node(new Point(w1_nx, w1_ny), new Point(w2_nx, w2_ny), n.t + 1));
}
}
}
//회전
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
Node next_n = new Node();
if(i==0) next_n = first_wing_rotation(n, j);
else next_n = second_wing_rotation(n, j);
if (!visited[next_n.w1.y][next_n.w1.x][next_n.w2.y][next_n.w2.x]) {
visited[next_n.w1.y][next_n.w1.x][next_n.w2.y][next_n.w2.x] = true;
que.add(next_n);
}
}
}
}
}
static Node first_wing_rotation(Node n, int dir) {
if (n.w1.y == n.w2.y) {
//가로
if (dir == 0) {
//시계 방향
if (range_check(new Point(n.w1.x, n.w1.y - 1))) {
//대각선 확인 돌아갈 수 있다면
if (range_check(new Point(n.w1.x + 1, n.w1.y - 1))) {
//돌아갔을 때 w1 위치가 가능한 위치라면
return new Node(new Point(n.w1.x + 1, n.w1.y - 1), new Point(n.w2.x, n.w2.y), n.t + 1);
}
}
} else if (dir == 1) {
//반시계 방향
if (range_check(new Point(n.w1.x, n.w1.y + 1))) {
if (range_check(new Point(n.w1.x + 1, n.w1.y + 1))) {
return new Node(new Point(n.w2.x, n.w2.y), new Point(n.w1.x + 1, n.w1.y + 1), n.t + 1);
}
}
}
} else {
//세로
if (dir == 0) {
//시계 방향
if (range_check(new Point(n.w1.x + 1, n.w1.y))) {
if (range_check(new Point(n.w1.x + 1, n.w1.y + 1))) {
return new Node(new Point(n.w2.x, n.w2.y), new Point(n.w1.x + 1, n.w1.y + 1), n.t + 1);
}
}
} else if (dir == 1) {
//반시계 방향
if (range_check(new Point(n.w1.x - 1, n.w1.y))) {
if (range_check(new Point(n.w1.x - 1, n.w1.y + 1))) {
return new Node(new Point(n.w1.x - 1, n.w1.y + 1), new Point(n.w2.x, n.w2.y), n.t + 1);
}
}
}
}
return new Node();
}
static Node second_wing_rotation(Node n, int dir) {
if (n.w1.y == n.w2.y) {
//가로
if (dir == 0) {
//시계 방향
if (range_check(new Point(n.w2.x, n.w2.y + 1))) {
if (range_check(new Point(n.w2.x - 1, n.w2.y + 1))) {
return new Node(new Point(n.w1.x, n.w1.y), new Point(n.w2.x - 1, n.w2.y + 1), n.t + 1);
}
}
} else if (dir == 1) {
//반시계 방향
if (range_check(new Point(n.w2.x, n.w2.y - 1))) {
if (range_check(new Point(n.w2.x - 1, n.w2.y - 1))) {
return new Node(new Point(n.w2.x - 1, n.w2.y - 1), new Point(n.w1.x, n.w1.y), n.t + 1);
}
}
}
} else {
//세로
if (dir == 0) {
//시계 방향
if (range_check(new Point(n.w2.x - 1, n.w2.y))) {
if (range_check(new Point(n.w2.x - 1, n.w2.y - 1))) {
return new Node(new Point(n.w2.x - 1, n.w2.y - 1), new Point(n.w1.x, n.w1.y), n.t + 1);
}
}
} else if (dir == 1) {
//반시계 방향
if (range_check(new Point(n.w2.x + 1, n.w2.y))) {
if (range_check(new Point(n.w2.x + 1, n.w2.y - 1))) {
return new Node(new Point(n.w1.x, n.w1.y), new Point(n.w2.x + 1, n.w2.y - 1), n.t + 1);
}
}
}
}
return new Node();
}
static boolean range_check(Point p) {
if ((0 <= p.x && p.x <= N - 1) && (0 <= p.y && p.y <= N - 1)) {
if (board[p.y][p.x] == 0) return true;
}
return false;
}
}