백준 16954번: 움직이는 미로 탈출

문제 설명

• https://www.acmicpc.net/problem/16954
• 왼쪽 아래에서 시작해 오른쪽 위에 도달할 수 있는지를 판단하는 문제입니다.
• 사람은 해당 위치에서 움직이지 않는 경우를 포함해 총 9가지 방향으로 움직일 수 있습니다.
• 사람은 다음 위치에로는 움직일 수 없습니다.
  • 현재 벽으로 가로막혀 있는 공간
  • 현재는 벽이 아니지만 1초 후 벽이 되는 공간

접근법

• 어떤 위치로 이동할 수 있을려면 해당 위치가 현재 벽이 아니다 + 내가 이동한 직후 벽으로 바뀌지 않는다라는 두 조건을 모두 만족해야 합니다.
• 일반적인 BFS는 해당 위치가 현재 벽이 아니다를 확인한 뒤 해당 좌표를 다시 큐에 삽입합니다.
  하지만 두번째 조건도 확인하기 위해 좌표를 임시 저장하고 벽을 움직인 뒤에도 여전히 유효한 값들만 큐에 삽입했습니다.
• 해당 문제에서는 제자리에 가만히 있는 움직임이 존재합니다.
  이것 역시 일반적인 BFS의 방문처리를 활용하면 이미 방문된 좌표로 취급되어 큐에 삽입되지 못합니다.
• 2차원 배열에서 벽과 사람의 위치를 갱신하지 않고, 벽과 사람의 위치좌표만 갱신하는 방식으로 문제를 풀었습니다.

정답

import java.util.*;
import java.io.*;

public class Main {
	static int[] dx = { 1, 1, 1, 0, 0, 0, -1, -1, -1 };
	static int[] dy = { 1, 0, -1, 1, 0, -1, 1, 0, -1 };
	static int N = 8;
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[][] board = new char[N][N];
		List<int[]> wall = new LinkedList<int[]>(); // 벽의 좌표 모음
		for (int i = 0; i < N; i++) {
			board[i] = br.readLine().toCharArray();
			for (int j = 0; j < N; j++) {
				if(board[i][j] == '#') {
					wall.add(new int[] {i,j});
				}
			}
		}
		
		System.out.println(BFS(wall));

	}
	

	public static int BFS(List<int[]> wall) {
		Queue<int[]> q = new LinkedList<int[]>();
		q.add(new int[] {7,0});
		boolean[][] v = new boolean[N][N];
		v[7][0] = true;
		while(!q.isEmpty()) {
			int size = q.size();
			List<int[]> tempList = new LinkedList<int[]>();
			while(--size>=0) {			
				int[] now = q.poll();
				if(now[0] == 0 && now[1] == 7) {
					return 1;
				}
				for (int d = 0; d < 9; d++) {
					int nx = now[0]+dx[d];
					int ny = now[1]+dy[d];
					if(0<=nx && nx<N && 0<=ny && ny <N && !isBlocked(new int[] {nx,ny}, wall)) {
						if((nx == now[0] && ny == now[1])||!v[nx][ny]) { // 제자리에 가만히 있는건 방문여부에 영향을 받지 않아야 한다
							tempList.add(new int[] {nx,ny}); // 현재 상태(벽이 움직이기 전)에서 이동할 수 있는 좌표
						}
					}
				}
			}
			
			wallMove(wall); // 벽이 이동함
			
			for (int i = 0; i < tempList.size(); i++) {
				int[] now = tempList.get(i);
				if(!isBlocked(now,wall)) {
					v[now[0]][now[1]] = true; // 벽이 이동한 뒤에도 유효한 좌표
					q.add(now);
				}
			}
		}
		
		return 0;
		
	}
		
	public static void wallMove(List<int[]> wall) { // 모든 벽이 아래로 한칸 움직임
		for (int i = 0; i < wall.size(); i++) {
			int[] now = wall.get(i);
			if(now[0]+1<N) {
				now[0] += 1;
			}else {
				wall.remove(i);
				i--;
			}
		}
	}
	
	public static boolean isBlocked(int[] now, List<int[]> wall) { // 벽으로 가로막혔는지 확인
		for (int i = 0; i < wall.size(); i++) {
			int[] temp = wall.get(i);
			if(now[0] == temp[0] && now[1] == temp[1]) {
				return true;
			}
		}
		return false;
	}
}

기타

• 제자리에 가만히 있는게 방문처리되지 않는다는 건 제자리값이 큐에 무한으로 삽입된다는 의미이다.
  하지만 내 코드는 정답처리 되었고, 그 이유를 생각해본 결과 아래와 같다.

  • 1. 해당 column에 벽이 존재하면 제자리값은 무조건 소멸된다. (위에서 내려오던 벽에 언젠가 가로막히기 때문에)
  • 2. 8초를 소멸하지 않고 버티면 무조건 목적지에 도달할 수 있다.
       8초 뒤에는 모든 벽이 소멸되 아무런 벽도 남아있지 않는 상태가 되기 때문에 q에 제자리값이 무한이 쌓이던 와중 return문을 만나 탈출하게 된다.

• 예시

.#......					........
.#......					........
.#......       8초 후에      ........
.#......       ------->     ........
.#......					........
.#......					........
.#......					........
.#......					........

• 위 케이스의 경우 무한히 왼쪽 아래 시작점에 머물 수 있고, 8초가 지나도 여전히 시작점에서 제자리 방문이 진행되지만, 그 와중에 다른 길로 값이 뻗어나가면서 결국 우측 상단에 도달할 수 있게 된다.