🤔 BOJ16954 움직이는 미로 탈출 (Java)

📌 문제

색상	의미
	구현
	주의할 점
	결론

욱제는 학교 숙제로 크기가 8×8인 체스판에서 탈출하는 게임을 만들었다. 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 욱제의 캐릭터는 가장 왼쪽 아랫 칸에 있고, 이 캐릭터는 가장 오른쪽 윗 칸으로 이동해야 한다.

이 게임의 특징은 벽이 움직인다는 점이다. 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 가장 아래에 있어서 아래에 행이 없다면 벽이 사라지게 된다. 욱제의 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 이동할 때는 빈 칸으로만 이동할 수 있다.

1초 동안 욱제의 캐릭터가 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

욱제의 캐릭터가 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지 구해보자.

📌 입력

8개 줄에 걸쳐서 체스판의 상태가 주어진다. '.'은 빈 칸, '#'는 벽이다. 가장 왼쪽 아랫칸은 항상 벽이 아니다.

📌 출력

욱제의 캐릭터가 가장 오른쪽 윗 칸에 도착할 수 있으면 1, 없으면 0을 출력한다.

📌 예제 입력

https://www.acmicpc.net/problem/16954

https://www.acmicpc.net/problem/16954

https://www.acmicpc.net/problem/16954

https://www.acmicpc.net/problem/16954

https://www.acmicpc.net/problem/16954

 

📌 요약

• 체스판의 크기는 8x8로 이루어져있다.
• '.' 은 빈칸, '#' 은 벽을 의미한다.
• 1초마다 벽은 아래로 내려온다.
• 케릭터는 (상하좌우, 대각선, 그대로) 이동할 수 있다.
• 움직이면 1초가 소모되며, 다음으로 벽이 내려온다.
• 케릭터는 왼쪽 아래(7, 0)에 위치하며, 오른쪽 위(0, 7)에 도착할 수 있는지 알아내야 한다.

 

📌 풀이

1. BFS로 풀면 되겠다고 생각이 들었다.
2. 그대로 구현해도 되겠지만, 3차원 배열을 이용해서 n초에 벽이 내려왔는지 상태를 저장했다.
   (예를 들자면 wall[x][y][k]는 (x, y)에 k초에 벽이 내려왔는지 상태를 저장할 수 있다.)
3. 먼저 큐에 가장 왼쪽(7, 0)에 현재 시간 0초를 넣는다.
4. 큐를 순회하면서 시간이 8초가 넘어가는 경우랑 도착 지점까지 왔다면 도착할 수 있다고 판단한다.
   왜냐하면 8x8 체크판으로 이루어져 있기 때문에 가장 위에 있는 벽도 7초면 맨 아래까지 도착 할 수 있다.
5. 이전에 그대로 움직였을 경우를 위해, k초에 벽이 존재하면 다른 방향을 확인하지 않도록 구현했다.
6. 이후로는 (상하좌우, 대각선, 그대로) 움직이면서 범위가 넘어가는지 체크하고, k초에 벽이 존재하는지 확인한다.
7. 조건에 맞으면 현재 시간 + 1을 해서 큐에 넣는다.

📌 코드

import java.util.LinkedList;
import java.util.Queue;

public class BOJ16954 {

	int[] dx = {0, -1, 0, 1, 1, -1, 1, -1};
	int[] dy = {1, 0, -1, 0, 1, -1, -1, 1};

	public int solution(char[][] board) {
		int max = 8;
		boolean[][][] wall = init(board, max);
		Queue<Person> q = new LinkedList<>();
		q.offer(new Person(7, 0, 0)); //왼쪽 아래에서 출발

		while (!q.isEmpty()) {
			Person cur = q.poll();

			if (cur.time >= max || cur.x == 0 && cur.y == 7) return 1; //8초 이상이거나 오른쪽 위로 도착하면 가능한 것으로 판단
			if (wall[cur.x][cur.y][cur.time]) continue; //해당 시간에 벽이 존재하면 다른 방향은 확인하지 않는다.

			for (int i = 0; i < max; i++) { //상하좌우, 대각선 확인
				int nx = cur.x + dx[i];
				int ny = cur.y + dy[i];

				if (nx < 0 || ny < 0 || nx >= max || ny >= max) continue; //범위 벗어나는지 확인하기
				if (wall[nx][ny][cur.time]) continue; //해당 시간에 벽이 존재하는 확인
				q.offer(new Person(nx, ny, cur.time + 1));
			}
			q.offer(new Person(cur.x, cur.y, cur.time + 1)); //시간을 늘리고, 움직이지 않는 경우 큐에 넣기
		}
		return 0;
	}

	private boolean[][][] init(char[][] board, int max) {
		boolean[][][] result = new boolean[max][max][max];

		for (int i = 0; i < max; i++) {
			for (int j = 0; j < max; j++) {

				if (board[i][j] == '#') { //맨 아래까지 벽을 이동하여 시간을 체크한다.
					int time = 0;
					for (int k = i; k < max; k++) {
						result[k][j][time++] = true;
					}
				}
			}
		}
		return result;
	}

	static class Person {
		int x, y, time; //x,y 좌표와 현재 시간

		public Person(int x, int y, int time) {
			this.x = x;
			this.y = y;
			this.time = time;
		}
	}
}

 

16954번: 움직이는 미로 탈출