[백준] 16945번 - 움직이는 미로 탈출 (java)

Baekjoon 16954 - 움직이는 미로 탈출 (클릭 시 이동)

문제

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

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

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

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

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
2 초	512 MB	7641	2365	1471	26.702%

입력

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

출력

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

풀이

1. 벽이 한칸씩 내려오는 메서드를 구현한다.
2. BFS 팔방을 탐색하며 방문체크되지 않은 곳을 방문한다.
3. 현재 위치가 벽이라면 건너뛴다.
4. 현재 위치를 다시 queue에 넣는다(가만히 있는다.)
5. 종착지에 도달할 수 있다면 1을 출력한다.

과정

1. 벽의 이동 ( 벽 : -1 , 땅 : 0)

static void move() {
    for (int c = 0; c < 8; c++) {
        if (maze[7][c] == -1) maze[7][c] = 0;
        for (int r = 6; r >= 0; r--) {
            if (maze[r][c] == -1) {
                maze[r+1][c] = -1;
                maze[r][c] = 0;
            }
        }
    }
}

2. bfs (벽 : -1, 땅 : 0, 그 외 : 9 ( 방문처리 ))

// 바로 아래칸으로는 내려가볼 필요가 없다.
// 아래로 내려가면 벽도 한칸 아래로 내려오므로 벽과 나 사이의 상대적 위치는 변하지 않기 때문.
static int[][] deltas = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, -1}, {0, -1}, {-1, -1}};

static int bfs() {
    Queue<Position> queue = new LinkedList<>();
    queue.offer(new Position(7, 0));
    maze[7][0] = 9;
    int size = 0;

    while (!queue.isEmpty()) {
        size = queue.size();
        for (int step = 0; step < size; step++) {
            Position temp = queue.poll();

            if (temp.r == 0 && temp.c == 7) return 1;    // 도착
            if (maze[temp.r][temp.c] == -1) continue;    // 벽을 이동시키고 보니 현재위치가 벽
            queue.offer(temp); // 가만히 있어본다.

            for (int i = 0; i < 7; i++) {
                int nr = temp.r + deltas[i][0];
                int nc = temp.c + deltas[i][1];
                if (isIn(nr, nc) && maze[nr][nc] == 0) {
                    queue.offer(new Position(nr, nc));
                    maze[nr][nc] = 9;
                }
            }
        }
        move();
    }
    return 0;
}

최종 소스코드

package BJ_Practice.Gold;

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

public class BJ_G4_16954_움직이는_미로_탈출 {
    static int[][] maze = new int[8][8];
    static int[][] deltas = { {-1, 0}, {-1, 1}, {0, 1}, {1, 1}, {1, -1}, {0, -1}, {-1, -1}};

    static class Position {
        int r, c;

        public Position(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }

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

        for (int i = 0; i < 8; i++) {
            String str = br.readLine();
            for (int j = 0; j < 8; j++) {
                if (str.charAt(j) == '.') maze[i][j] = 0;
                else maze[i][j] = -1;
            }
        }

        System.out.println(bfs());
    }

    static int bfs() {
        Queue<Position> queue = new LinkedList<>();
        queue.offer(new Position(7, 0));
        maze[7][0] = 9;
        int size = 0;

        while (!queue.isEmpty()) {
            size = queue.size();
            for (int step = 0; step < size; step++) {
                Position temp = queue.poll();

                if (temp.r == 0 && temp.c == 7) return 1;
                if (maze[temp.r][temp.c] == -1) continue;
                queue.offer(temp);

                for (int i = 0; i < 7; i++) {
                    int nr = temp.r + deltas[i][0];
                    int nc = temp.c + deltas[i][1];
                    if (isIn(nr, nc) && maze[nr][nc] == 0) {
                        queue.offer(new Position(nr, nc));
                        maze[nr][nc] = 9;
                    }
                }
            }
            move();
        }
        return 0;
    }

    static void move() {
        for (int c = 0; c < 8; c++) {
            if (maze[7][c] == -1) maze[7][c] = 0;
            for (int r = 6; r >= 0; r--) {
                if (maze[r][c] == -1) {
                    maze[r+1][c] = -1;
                    maze[r][c] = 0;
                }
            }
        }
    }

    static boolean isIn(int r, int c) {
        return r >= 0 && r < 8 && c >= 0 && c < 8;
    }
}