[백준 - Java] 16954번 : 움직이는 미로 탈출

문제

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

설명

BFS를 이용해 문제를 해결했다.

• while문 안에서 큐의 크기만큼 for문을 사용한 이유 : 욱이의 캐릭터가 먼저 움직이고 벽이 아래로 이동하기 때문에 먼저 큐의 크기만큼 욱이의 캐릭터를 이동시켜본 뒤에 for문 밖에서 벽을 아래로 이동시키는 것이다.
  -> 큐가 빌 때까지 욱이의 캐릭터가 가장 오른쪽 윗 칸에 도달하지 못한 경우 false를 반환한다.
• 방문 처리를 해줄 필요가 없다.
  -> 제자리에 있는 경우에도 큐에 추가되어야 하기 때문에 방문 처리를 하면 안 된다. 만약 visited 배열을 사용해 방문처리를 해줄 경우 제자리에 있는 경우에는 큐에 추가할 수 없기 때문에 아래와 같은 예시에서는 0이 출력된다.

........
........
........
........
........
#.......
.#......
.#......

정답 : 1
오답 : 0

방문 처리를 해줄 경우 (7, 0)의 상하좌우, 제자리, 대각선을 확인하면서 큐에 (6, 0)만 추가가 되는데 캐릭터가 이동하고 벽이 (6, 0)으로 내려오면 캐릭터는 더 이상 움직일 수 없으므로 0이 출력된다. (큐에 (6, 0)만 추가되어 있었던 상황이므로 while문 조건인 !q.isEmpty()에 위배되기 때문에 0이 출력되는 것이다.)

소스코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;

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

public class Main {

    // 상, 하, 좌, 우, 왼쪽 위, 왼쪽 아래, 현재 위치, 오른쪽 위, 오른쪽 아래
    static int[] dx = {-1, 0, 1, 0, 0, -1, 1, -1, 1};
    static int[] dy = {0, -1, 0, 1, 0, -1, -1, 1, 1};
	
    static char[][] map;
	
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        map = new char[8][8];
        
		for (int i = 0; i <  8; i++) {
            map[i] = br.readLine().toCharArray();
        }
		
        System.out.println(bfs() ? 1 : 0);
    }
	
    public static boolean bfs() {
        Queue<Point> q = new LinkedList<>();
		
        q.add(new Point(7, 0)); // 욱제의 캐릭터 시작 위치 추가
		
        while (!q.isEmpty()) {
            int size = q.size();
			
            // 욱이의 캐릭터를 먼저 움직여야 하므로 큐의 크기만큼 반복
            for (int i = 0; i < size; i++) {
                Point p = q.poll();
                int x = p.x;
                int y = p.y;
				
                // 가장 오른쪽 윗 칸으로 이동한 경우 종료
                if (x == 0 && y == 7) {
                    return true;
                }
				
                // 벽이 있는 경우 이동할 수 없기 때문에 넘어감
                if (map[x][y] == '#') {
                    continue;
                }
				
                // 모든 방향을 다 보면서 이동할 수 있는지 확인
                for (int j = 0; j < 9; j++) {
                    int nx = x + dx[j];
                    int ny = y + dy[j];
					
                    // 범위를 벗어나지 않고, 빈 칸일 경우
                    if (nx >= 0 && nx < 8 && ny >= 0 && ny < 8 && map[nx][ny] == '.') {
                        q.add(new Point(nx, ny));
                    }
					
                }
            }
			
            // 욱이의 캐릭터를 이동시킨 후 벽을 아래 행으로 한 칸씩 내림
            for (int i = 7; i >= 0; i--) {
                for (int j = 0; j < 8; j++) {
                    // 처음에 가장 맨 위의 행에 벽이 있어도 1초 뒤에는 벽이 내려가므로 첫 번째 행은 무조건 '.'으로 바꿔줌
                    if (i == 0) {
                        map[i][j] = '.';
                    }
                    else {
                        // 이전 행에 있던걸 넣어줌
                        map[i][j] = map[i - 1][j];	
                    }
                }
            }
        
        }
		
        return false;
    
    }

}

GITHUB

https://github.com/MinchaeGwon/BOJ/blob/master/BOJ%2316954/src/Main.java