[백준] 16954번: 움직이는 미로 탐색 (Java)

1. 문제설명

크기가 8x8인 체스판의 모든 칸은 빈 칸 또는 벽 중 하나이다. 체스판 가장 왼쪽 아래 칸에서 가장 오른쪽 윗 칸으로 이동하는 게임을 진행한다. 이 게임에서 1초마다 모든 벽이 아래에 있는 행으로 한 칸씩 내려가고, 아래에 행이 없다면 벽이 사라진다. 캐릭터는 1초에 인접한 한 칸 또는 대각선 방향 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다. 1초 동안 먼저 이동하고, 그 다음 벽이 이동한다. 벽이 캐릭터가 있는 칸으로 이동하면 더 이상 캐릭터는 이동할 수 없다.

캐릭터가 목표 지점까지 이동할 수 있는지 없는지 구하는 문제이다.

• 시간 제한: 2초
• 메모리 제한: 512MB

 

2. 접근 방식

• 캐릭터를 (7, 0) 위치에서 출발시킨다. BFS 수행.
• 캐릭터가 이동할 수 있는 위치(상하좌우, 대각선, 제자리)를 확인하고, 해당 위치로 이동한다.
• 한 라운드가 끝나면 벽을 한 칸 아래 행으로 이동시킨다.
• 이동 가능한 위치가 없거나, 벽이 캐릭터의 위치에 도달하면 실패로 간주한다.
• 캐릭터가 도착 지점 (0, 7)에 도달하면 성공으로 간주한다.

 

3. 최종 코드

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

public class Main {
    static char[][] board = new char[8][8]; // 체스판 배열
    static boolean[][] visited; // 방문 여부 확인하는 배열
    static Queue<int[]> q = new ArrayDeque<>(); // bfs에서 사용할 큐 선언

    // 상하좌우, 대각선, 제자리
    static int[] dx = {-1, 1, 0, 0, -1, -1, 1, 1, 0};
    static int[] dy = {0, 0, -1, 1, -1, 1, -1, 1, 0};

    static void bfs() {
        while(!q.isEmpty()) { // 큐가 빌 때까지
            int size = q.size();

            // 현재 큐에 있는 모든 상태를 처리
            for(int i=0; i<size; i++) {
                int[] c = q.poll();

                // 1. 목표지점에 도달하면 1을 출력하고 종료
                if(c[0]==0 && c[1]==7) {
                    System.out.println(1);
                    return;
                }

                // 2. 캐릭터를 상하좌우 또는 대각선 또는 제자리 이동 시도
                for(int j=0; j<9; j++) {
                    int nx = c[0] + dx[j];
                    int ny = c[1] + dy[j];
                    // 체스판 범위 내에 있고
                    if(nx>=0 && nx<8 && ny>=0 && ny<8) {
                        // 벽이 아니고, 방문하지 않은 경우
                        if(board[nx][ny]=='.' && !visited[nx][ny]) {
                            visited[nx][ny] = true; // 방문 처리
                            q.add(new int[]{nx, ny}); // 큐에 추가
                        }
                    }
                }
            }

            // 3. 더 이상 이동할 곳이 없으면
            if(q.isEmpty()) {
                // 0을 출력하고 종료
                System.out.println(0);
                return;
            }

            // 4. 벽을 한 칸 아래 행으로 이동
            for(int i=0; i<8; i++) {
                for(int j=0; j<8; j++) {
                    if(board[i][j]=='#') {
                        board[i][j] = '.';
                        if(i+1<8) {
                            board[i+1][j] = '#';
                        }
                    }
                }
            }

            // 5. 벽이 내려와서 캐릭터가 있는 위치에 도달하면
            for(int[] pos : q) {
                if(board[pos[0]][pos[1]] == '#') {
                    // 0을 출력하고 종료
                    System.out.println(0);
                    return;
                }
            }
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        for(int i=0; i<8; i++) {
            String s = br.readLine();
            for(int j=0; j<8; j++) {
                board[i][j] = s.charAt(j);
            }
        }

        q.add(new int[]{7, 0}); // 시작 위치를 큐에 추가
        visited = new boolean[8][8]; // 방문 확인 배열 초기화
        bfs();
    }
}