[Java] BOJ16954, 백준 - 움직이는 미로 탈출

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

16954번: 움직이는 미로 탈출

 

효율성의 함정에 빠져서 어떻게 브루트포스로 안풀고 해결하지 고민하다가 오래걸린 문제,,, 그냥 가능한 경로를 일일이 해보면 되는 문제였다 😓

 

1. 욱제가 상/하/좌/우/대각선4방향/그대로 총 9 방향으로 움직이거나 멈춰있을 수 있습니다. 현재 있는 칸과 움직일 칸 모두에 벽이 있으면 안됩니다.

	// 현재의 칸(p.i,p.j)에서 9방향으로 돌려가며 ni와 nj를 찾는다.
	int ni = p.i + move[i][0];
	int nj = p.j + move[i][1];

	if (ni < 0 || nj < 0 || ni >= 8 || nj >= 8)
		continue;

	// 다음 칸에 도달하기까지의 경로나
	if (ni - time >= 0 && map[ni - time][nj] == '#')
		continue;
    // 도착할 칸에 벽이 있으면 안됨
	if (ni - time + 1 >= 0 && map[ni - time + 1][nj] == '#')
		continue;

 

2. 시간이 지날때마다 벽이 한 칸씩 내려오고, 9초가 된 시점에서는 맵에 아무런 벽도 존재하지 않게 됩니다.

 9초가 된 시점에서는 맵에 아무런 벽도 존재하지 않게 됩니다.

이 말을 다시 생각해보면 t의 시간이 지났을 때 행의 인덱스가 (0~t-1)인 구간에는 벽이 존재하지 않는다는 말이 됩니다.
또한 t초가 지났을때 맵이 통째로 t열 내려오기 때문에 i열의 형태는 map[i-t]가 됩니다.

이렇게 발견한 규칙을 바탕으로  모든 경우의 수에 대한 BFS를 수행하면 됩니다. 왔던길을 되돌아갔다가 다시 온다던지 가만히있는다던지의 경우의 수가 있기 때문에 따로 visit check를 하지 않았습니다.
맵의 크기가 8*8으로 고정되어 있는 점, 욱제의 시작점이 (7,0)으로 고정되어 있는 점, ni<time이면 함수를 종료할 수 있다는 점에서 별다른 visit배열 없이 이동할 수 있는 모든 경로의 경우의 수를 구해도 상관없다고 생각했습니다.

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

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		char[][] map = new char[8][8];
		for (int i = 0; i < 8; i++)
			map[i] = br.readLine().toCharArray();

		Queue<Point> q = new LinkedList<>();
		q.offer(new Point(7, 0));

		int[][] move = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 }, { 1, 1 }, { -1, 1 }, { 1, -1 }, { -1, -1 },
				{ 0, 0 } };

		// 벽을 먼저 이동시키고 욱제를 체크
		for (int time = 1; time < 9; time++) {
			int size = q.size();

			if (size == 0) {
				System.out.println(0);
				return;
			}

			for (int s = 0; s < size; s++) {
				Point p = q.poll();
				for (int i = 0; i < 9; i++) {
					int ni = p.i + move[i][0];
					int nj = p.j + move[i][1];

					if (ni < 0 || nj < 0 || ni >= 8 || nj >= 8)
						continue;

					if (ni - time >= 0 && map[ni - time][nj] == '#')
						continue;
					if (ni - time + 1 >= 0 && map[ni - time + 1][nj] == '#')
						continue;

					if (ni < time) {
						System.out.println(1);
						return;
					}
					q.offer(new Point(ni, nj));
				}
			} // 현재 시간에서 이동할 수 있는 경우의수를 전부 비교
		}

		System.out.println(1);
	}

	static class Point {
		int i, j;

		Point(int i, int j) {
			this.i = i;
			this.j = j;
		}
	}
}