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

문제 링크

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

알고리즘: BFS

문제

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

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

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

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

풀이

캐릭터가 중복 없이 이동할 수 있는 위치라면 Queue에 다 넣어준다.
=> 벽이 아닌 위치면서 범위 안쪽이라면 전부 이동할 수 있는 위치임, visited로 중복을 방지해준다.
현재 위치에서 이동할 수 있는 위치를 Queue에 다 넣었다면.
벽을 움직여주고 visited는 초기화 시켜준다.
벽을 움직이고 나면 벽이랑 캐릭터의 위치가 같은 경우도 발생하는데 그 경우는 continue를 통해 pass를 해주고 겹치지 않는다면 다시 위 탐색 방법을 반복해준다.
목표 지점으로 이동할 수 있는 경우는 Queue의 사이즈가 0이 아니면서 동시에 벽이 존재하지 않는다면 무조건 목표 지점에 도달할 수 있고, 벽이 있음에도 목표 지점에 캐릭터가 도달했다면 그 경우도 똑같이 return 1; 처리를 해준다.
Queue의 사이즈가 0으로 while문이 return 1; 없이 종료됐다면 캐릭터는 목표 지점에 도달할 수 없는 경우이기 때문에 return 0;을 처리해주면 해당 문제를 통과할 수 있다.

소스코드

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

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

public class Main {
    static final int dx[] = {0, 0, 0, -1, 1, -1, -1, 1, 1}; //제자리, 위, 아래, 왼, 오, 대각선 왼쪽 위, 대각선 왼쪽 아래, 대각선 오른쪽 위, 대각선 오른쪽 아래
    static final int dy[] = {0, -1, 1, 0, 0, -1, 1, -1, 1};
    static char board[][] = new char[8][8];
    static boolean visited[][] = new boolean[8][8];
    static ArrayList<Coordinate> wall_coor = new ArrayList<Coordinate>();
    static ArrayList<Coordinate> visited_true = new ArrayList<Coordinate>();
    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);
              if(board[i][j] == '#') {
                  wall_coor.add(new Coordinate(j, i));
              }
          }
      }
      System.out.println(BFS());
    }
    
    static int BFS() {
        Queue<Coordinate> que = new LinkedList<>();
        que.add(new Coordinate(0,7));
        while(!que.isEmpty()) {
            int sz = que.size();
            for(int j=0; j<sz; j++) {
                Coordinate v = que.poll();
                if((wall_coor.size() == 0) || ((v.x == 7) && (v.y == 0))) {
                    return 1;
                }
                if(board[v.y][v.x] == '#') {
                    continue;
                }
                for(int i=0; i<dx.length; i++) {
                    int nx = v.x + dx[i];
                    int ny = v.y + dy[i];
                    if((nx>=0 && nx<=7) && (ny>=0 && ny<=7)) {
                        if(board[ny][nx] != '#' && !visited[ny][nx]) {
                            visited[ny][nx] = true;
                            visited_true.add(new Coordinate(nx, ny));
                            que.add(new Coordinate(nx, ny));
                        }
                    }
                }
            }
            move_wall();
            back_visited();
        }
        return 0;
    }
    
    static void move_wall() {
        if(wall_coor.size() != 0) {
            ArrayList<Coordinate> nWall_coor = new ArrayList<Coordinate>();
            for(int i=0; i<wall_coor.size(); i++) {
                board[wall_coor.get(i).y][wall_coor.get(i).x] = '.';
            }
            for(int j=0; j<wall_coor.size(); j++) {
                int ny = wall_coor.get(j).y + 1;
                if(ny <= 7) {
                    board[ny][wall_coor.get(j).x] = '#';
                    nWall_coor.add(new Coordinate(wall_coor.get(j).x, ny));
                }
            }
            wall_coor = nWall_coor;
        }
    }
    
    static void back_visited() {
        for(int i=0; i<visited_true.size(); i++) {
            visited[visited_true.get(i).y][visited_true.get(i).x] = false;
        }
        visited_true = new ArrayList<Coordinate>();
    }
}