[프로그래머스] 60063번 - 블록 이동 (Java)

 

 

반응형

 

 

---

⬛ 문제

 

 

https://programmers.co.kr/learn/courses/30/lessons/60063

코딩테스트 연습 - 블록 이동하기

 

 

 

---

⬛ 풀이

 

BFS 심화 문제였다. 

 

기존 BFS 문제들은 좌표 하나를 가지고 탐색을 하지만 이번 문제는 두 좌표를 가지고 탐색을 하는 문제였다.

 

또한 로봇은 가로 or 세로 타입을 가지기 때문에 방문탐색은 3차원 배열 boolean[2][][]을 통해 관리하였다. visited 배열에서 각 타입별로 체크할 때 두 좌표가 모두 방문을 했을 때만 방문했었다고 판단하고, 하나라도 방문하지 않은 점을 가지면 진행할 수 있다.

 

4방 탐색을 할 때 최대 3가지 좌표를 큐에 삽입할 수 있다. 

 

예를 들어 현재 좌표가 (r1, c1), (r2, c2), 로봇의 타입이 가로(0)이고, 탐색 방향 d = 0, 1(하, 상)일 때 아래 3가지 경우가 가능하다.

 

1. 방향전환을 하지 않은 (nr1, nc1), (nr2, nc2)
2. 첫 번째 좌표를 축으로 회전한 (r1, c1), (nr1, nc1)
3. 두 번째 좌표를 축으로 회전한 (r2, c2), nr2, nc2)

 

 

마찬가지로 로봇의 타입이 세로(1)이고, 탐색 방향 d = 2, 3(좌, 우)일 때도 최대 3가지 경우가 가능하다.

 

프로그램 전체 로직은 다음과 같다.

 

1. 최소 시간을 구하는 문제이므로 BFS로 해결하였다.

2. 가로, 세로 2가지 형태로 이동하므로 3차원 boolean[2][][]로 방문체크를 한다.

3. 2개의 좌표값을 가지고 이동하기 때문에 한 점이라도 방문하지 않은 곳이면 진행이 가능하다.

4. 큐에 상하좌우로 이동한 좌표값과 회전 가능한 좌표값을 넣어주고 끝점에 도달하면 종료한다.

 

 

 

---

⬛ 코드

 

import java.util.*;

public class Solution {

	public int solution(int[][] board) {
		int n = board.length;
		int answer = 0;
		boolean[][][] visited = new boolean[2][n][n]; // 0: 가로, 1: 세로
		int[] dr = { -1, 1, 0, 0 }; // 하, 상, 좌, 우
		int[] dc = { 0, 0, -1, 1 };
		int[][] start = new int[][] { { 0, 0 }, { 0, 1 }, { 0 } }; // 2개의 좌표값과 소요시간

		Queue<int[][]> q = new ArrayDeque<>();
		q.offer(start);
		visited[0][0][0] = true;
		visited[0][0][1] = true;

		// BFS
		while (!q.isEmpty()) {
			int[][] cur = q.poll();
			int r1 = cur[0][0];
			int c1 = cur[0][1];
			int r2 = cur[1][0];
			int c2 = cur[1][1];
			int type = type(cur[0], cur[1]);
			int time = cur[2][0];

			if ((r1 == n - 1 && c1 == n - 1) || (r2 == n - 1 && c2 == n - 1)) {
				answer = time;
				break;
			}

			for (int d = 0; d < 4; d++) {
				int nr1 = r1 + dr[d];
				int nc1 = c1 + dc[d];
				int nr2 = r2 + dr[d];
				int nc2 = c2 + dc[d];

				if (oob(nr1, nc1, n) && oob(nr2, nc2, n) && board[nr1][nc1] != 1 && board[nr2][nc2] != 1) {
					// 로봇을 방향전환 없이 상하좌우 추가
					if ((!visited[type][nr1][nc1] || !visited[type][nr2][nc2])) {
						visited[type][nr1][nc1] = true;
						visited[type][nr2][nc2] = true;
						q.offer(new int[][] { { nr1, nc1 }, { nr2, nc2 }, { time + 1 } });
					}

					// 로봇이 가로이면서 방향이 상하 or 세로이면서 좌우일 때 회전 가능
					int typeChange = 1 ^ type;

					if ((type == 0 && d < 2) || (type == 1 && d > 1)) {
						if (!visited[typeChange][nr1][nc1] || !visited[typeChange][r1][c1]) {
							visited[typeChange][nr1][nc1] = true;
							visited[typeChange][r1][c1] = true;
							q.offer(new int[][] { { nr1, nc1 }, { r1, c1 }, { time + 1 } });
						}

						if (!visited[typeChange][nr2][nc2] || !visited[typeChange][r2][c2]) {
							visited[typeChange][nr2][nc2] = true;
							visited[typeChange][r2][c2] = true;
							q.offer(new int[][] { { nr2, nc2 }, { r2, c2 }, { time + 1 } });
						}
					}

				}
			}
		}

		return answer;
	}

	public boolean oob(int r, int c, int n) {
		return 0 <= r && r < n && 0 <= c && c < n;
	}

	// 두 좌표가 가로이면 0, 세로이면 1 반환
	public int type(int[] pos1, int[] pos2) {
		if (pos1[0] == pos2[0])
			return 0;
		return 1;
	}
}