[BOJ/BFS] 백준 16954 - 움직이는 미로 탈출 (Java)

16954 - 움직이는 미로 탈출

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

문제

8x8 체스판에서 탈출하는 게임/ 모든 칸은 빈 칸 or 벽 중 하나
시작: 가장 왼쪽 아랫 칸 / 도착: 가장 오른쪽 윗 칸
1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고 가장 아래에 있어서 행 X -> 벽 사라짐
1초에 인접한 한 칸 or 대각선 방향으로 인접한 한 칸 이동 or 현재 위치 서 있을 수 있음 (빈칸으로만 이동)
1초 동안 캐릭터 먼저 이동 -> 벽 이동/ 벽이 캐릭터 있는 칸으로 이동하면 캐릭터 이동 X
=> 가장 오른쪽 윗 칸으로 이동할 수 있는지 없는지

입력: 8개 줄에 걸쳐 체스판 상태 주어짐 ('.' 빈칸 / '#' 벽)/ 가장 왼쪽 아랫칸 항상 벽 X
출력: 가장 오른쪽 윗 칸 도착 O -> 1 / X -> 0

---

풀이

• 각 위치 + 시간 정보 저장

class Point {
    int x, y, t;

    Point (int x, int y, int t) {
        this.x = x;
        this.y = y;
        this.t = t;
    }
}

 

• 위, 아래, 좌, 우, 대각선 8방향 + 제자리 (0, 0)

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

 

BFS

• 시작 (7, 0) / 도착 (0, 7)
  • `cur.x == 0 && cur.y == 7`
• 최대 시간 8초 = 벽이 8칸 내려가면 모두 사라짐 -> `visited[8][8][9]`
  • `cur.t >= 8` 
  • `Math.min(8, cur.t + 1)`
• 이동 불가 조건
  • 현재 시간 t에서 (x, y)에 벽이 있는지 -> `map[x - t][y]`
    • t초 후에 아래로 t칸 이동
  • `cur.x - cur.t >= 0 && map[cur.x - cur.t][cur.y] == '#'`: 현재 위치 이미 벽
  • `nx - cur.t >= 0 && map[nx - cur.t][ny] == '#'`: 현재 시점에서 이동하려는 칸이 벽
  • `nx - nt >= 0 && map[nx - nt][ny] == '#'`: 다음 시점(벽이 한 칸 내려온 후) 벽

static boolean bfs() {
    Queue<Point> q = new LinkedList<>();
    boolean[][][] visited = new boolean[8][8][9];
    q.offer(new Point(7, 0, 0));
    visited[7][0][0] = true;

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

        if (cur.x == 0 && cur.y == 7) return true;
        if (cur.t >= 8) return true;

        for (int d = 0; d < 9; d++) {
            int nx = cur.x + dx[d];
            int ny = cur.y + dy[d];
            int nt = Math.min(8, cur.t + 1);

            if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) continue;
            if (cur.x - cur.t >= 0 && map[cur.x - cur.t][cur.y] == '#') continue;

            if (nx - cur.t >= 0 && map[nx - cur.t][ny] == '#') continue;
            if (nx - nt >= 0 && map[nx - nt][ny] == '#') continue;

            if (!visited[nx][ny][nt]) {
                visited[nx][ny][nt] = true;
                q.offer(new Point(nx, ny, nt));
            }
        }
    }

    return false;
}

---

코드

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

// 움직이는 미로 탈출
class Point {
    int x, y, t;

    Point (int x, int y, int t) {
        this.x = x;
        this.y = y;
        this.t = t;
    }
}

public class boj_16954 {
    static char[][] map = new char[8][8];
    static int[] dx = {0, -1, -1, -1, 0, 1, 1, 1, 0};
    static int[] dy = {-1, -1, 0, 1, 1, 1, 0, -1, 0};

    static boolean bfs() {
        Queue<Point> q = new LinkedList<>();
        boolean[][][] visited = new boolean[8][8][9];
        q.offer(new Point(7, 0, 0));
        visited[7][0][0] = true;

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

            if (cur.x == 0 && cur.y == 7) return true;
            if (cur.t >= 8) return true;

            for (int d = 0; d < 9; d++) {
                int nx = cur.x + dx[d];
                int ny = cur.y + dy[d];
                int nt = Math.min(8, cur.t + 1);

                if (nx < 0 || nx >= 8 || ny < 0 || ny >= 8) continue;
                if (cur.x - cur.t >= 0 && map[cur.x - cur.t][cur.y] == '#') continue;

                if (nx - cur.t >= 0 && map[nx - cur.t][ny] == '#') continue;
                if (nx - nt >= 0 && map[nx - nt][ny] == '#') continue;

                if (!visited[nx][ny][nt]) {
                    visited[nx][ny][nt] = true;
                    q.offer(new Point(nx, ny, nt));
                }
            }
        }

        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        for (int i = 0; i < 8; i++) {
            map[i] = br.readLine().toCharArray();
        }

        System.out.println(bfs() ? 1 : 0);
    }
}