[JAVA] BOJ 백준 16954번 - 움직이는 미로 탈출

목차

• 문제
• 내가 푼 방법
• 자바 코드
• 결과 및 회고

---

1. 문제

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

16954번: 움직이는 미로 탈출

---

2. 내가 푼 방법

캐릭터가 이동하고, 체스판이 움직이는 과정을 탈출할 수 있도록 하는 조건이 제일 관건인 문제라고 생각한다.

 

먼저 캐릭터가 이동하는 moveCharacter 함수는 BFS 알고리즘을 사용한다. 보통은 for문에서 다음 칸이 벽일 경우에 이동할 수 없는 것만 확인하면 된다. 하지만 이 문제는 체스판이 이동하기 때문에, 현재 캐릭터가 있는 칸이 벽일 경우가 존재한다. 따라서 arr[x][y]가 벽인 것도 동시에 확인해주어야 한다.

public static Queue<int[]> moveCharacter(Queue<int[]> queue) {
    Queue<int[]> res = new ArrayDeque<>();

    while (!queue.isEmpty()) {
        int[] q = queue.poll();
        int x = q[0];
        int y = q[1];

        if (arr[x][y] == '#') continue;

        for (int d = 0; d < dx.length; d++) {
            int nx = x + dx[d];
            int ny = y + dy[d];

            if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
            if (arr[nx][ny] == '#') continue;

            if (nx == 0 && ny == N-1) {
                possible = 1;
                break;
            }

            res.add(new int[]{nx, ny});
        }
    }

    return res;
}

 

체스판을 이동시키는 moveChess 함수는 이중 for문을 사용했으며, 핵심은 solution 함수에서 돌아가는 while문의 조건이다. 오른쪽 제일 위의 칸에 도착했다는 플래그가 세워지면 게임을 빠져나오고, 큐가 비어있을 경우에도 게임을 빠져나와야 한다. 캐릭터가 한 번씩 이동하고 나면 체스판을 이동시켜야 하므로 바깥쪽에서 큐를 선언해 공유될 수 있도록 한다.

public static void solution() {
    Queue<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{sx, sy});

    while (possible == 0 && !queue.isEmpty()) {
        queue = moveCharacter(queue);
        moveChess();
    }
}

---

3. 자바 코드

깃허브 풀이 주소 : https://github.com/geujeog/BOJ/blob/main/B16954.java

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

class Main {
    static int N = 8;
    static int sx, sy;
    static char[][] arr;
    static int possible;
    static int[] dx = {0, -1, 1, 0, 0, -1, -1, 1, 1};
    static int[] dy = {0, 0, 0, -1, 1, -1, 1, -1, 1};

    public static void main (String[] args) throws IOException {
        input();
        solution();
        output();
    }

    public static void solution() {
        Queue<int[]> queue = new ArrayDeque<>();
        queue.add(new int[]{sx, sy});

        while (possible == 0 && !queue.isEmpty()) {
            queue = moveCharacter(queue);
            moveChess();
        }
    }

    public static void moveChess() {
        for (int i = N-1; i >= 0; i--) {
            for (int j = 0; j < N; j++) {
                if (arr[i][j] == '#') {
                    arr[i][j] = '.';
                    if (i != N-1) arr[i+1][j] = '#';
                }
            }
        }
    }

    public static Queue<int[]> moveCharacter(Queue<int[]> queue) {
        Queue<int[]> res = new ArrayDeque<>();

        while (!queue.isEmpty()) {
            int[] q = queue.poll();
            int x = q[0];
            int y = q[1];

            if (arr[x][y] == '#') continue;

            for (int d = 0; d < dx.length; d++) {
                int nx = x + dx[d];
                int ny = y + dy[d];

                if (nx < 0 || ny < 0 || nx >= N || ny >= N) continue;
                if (arr[nx][ny] == '#') continue;

                if (nx == 0 && ny == N-1) {
                    possible = 1;
                    break;
                }

                res.add(new int[]{nx, ny});
            }
        }

        return res;
    }

    public static void output() throws IOException {
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        bw.write(possible+"");

        bw.flush();
        bw.close();
    }

    public static void input() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        sx = N-1;
        sy = 0;
        arr = new char[N][N];
        possible = 0;

        for (int i = 0; i < N; i++) {
            String line = br.readLine();

            for (int j = 0; j < N; j++) {
                arr[i][j] = line.charAt(j);
            }
        }

        br.close();
    }
}

---

4. 결과 및 회고

간단하게 풀이할 수 있었던 문제였다. 한 번에 통과해서 나이스하당