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

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

16954번: 움직이는 미로 탈출

 

문제풀이

BFS 문제였습니다.

한 턴마다 qSize를 저장해두어서 해당 qSize만큼만 움직이고, 처리하는 로직이 주 로직이었습니다.

처음에 벽이 있을때와 없을떄를 비교한다고 하여서 벽이 있을때의 Visited[][][2] 이런식으로 처리해야할까? 라는 생각을 했었습니다.

하지만, 벽의 위치는 계속 변하므로 위의 생각보다는 1초가 지날때마다 Visited를 새로 초기화하여서 BFS를 다시 시작해야 합니다.

또한, 문제에서 조건을보면,

- 1초에 인접한 한 칸 또는 대각선 방향으로 인접한 한 칸으로 이동하거나, 현재 위치에 서 있을 수 있다.

라는 조건이 있는데 현재 위치에 서있을 수 있다 라는 조건을 놓쳐서 조금 헷갈렸습니다.

: 그러므로 Visited[][] 처리는 이동한 이후에 처리해야합니다.

 

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

: 이 조건에서 보면, 욱제는 이미 벽이 없는 곳을 피해 BFS를 실행시키지만, 벽은 무조건 내려오므로 욱제가 Q.poll을 통해 값이 나올때마다 벽이 있는지 없는지 체크하여야합니다.(벽이 있다면 욱제는 더이상 움직일 수 없음을 처리)

 

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
	public static char[][] map;
	public static Queue<Node> q = new LinkedList<>();
	public static boolean[][] visited;
	public static int result = 0;
    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();
    	}
		
        //맨 왼쪽아래에서부터 시작
    	q.offer(new Node(7,0));
		simulate();	
		System.out.println(result);
    	
    }
    
    
    public static void simulate() {
    	//현재 위치 그대로 + 8 방향
    	int[] dx = {0,0,-1,-1,-1,0,1,1,1};
    	int[] dy = {0,-1,-1,0,1,1,1,0,-1};
    	
    	
    	//1초 동안 욱제의 캐릭터가 먼저 이동
    	while(!q.isEmpty()) {
    		int qsize = q.size();
  			
            //매번 Visited를 초기화(벽의 위치가 계속 초기화되기에)
    		visited = new boolean[8][8];
            
            //한턴에 움직일 q의 사이즈만큼만 이동합니다.
    		for(int i=0;i<qsize;i++) {
        		Node temp = q.poll();
        		int x = temp.x;
        		int y = temp.y;
        		
                //만약 현재 위치에 벽이 있다면, 중단
                //1초동안 욱제가 먼저 움직인 후, 벽이 캐릭터가있는 곳으로 이동하면
                //욱제는 이동할 수 없다는 조건이 있습니다.
        		if(map[x][y] == '#') continue;
        		if(x == 0 && y == 7) {
        			result = 1;
        			return ;
        		}
        		for(int dir=0;dir<=8;dir++) {
        			int nx = x + dx[dir];
        			int ny = y + dy[dir];
        			if( nx < 0 || nx >= 8 || ny < 0 || ny >= 8 ) continue;
        			if( map[nx][ny] == '#' || visited[nx][ny] == true) continue;
        			q.offer(new Node(nx, ny));
        			visited[nx][ny] = true;
        		}    			
    		}
    		
            //벽을 아래칸으로 내려주는 작업
    		for(int i=7;i>0;i--) {
    			for(int j=0;j<=7;j++) {
    				map[i][j] = map[i-1][j];
    				
    			}
    		}
    		for(int i=0;i<7;i++) {
    			map[0][i] = '.';
    		}
    		
    	}
    }
    
    
    
    
}
class Node{
	int x;
	int y;
	public Node(int x, int y) {
		this.x = x;
		this.y = y;
	}
}