[백준] 움직이는 미로 탈출 16954 java - bfs

맨 처음 bfs 기본 로직은 짰는데

매번 이동할 때마다 그래프를 이동하는 게 아니라

한 번의 턴 후에 그래프를 이동시켜야 하는데.. 이 부분 처리에서 헤맸다 ㅜㅜ

또한 한 번의 턴에서는 중복 처리를 제거해야지 메모리 초과가 발생하지 않으므로

한 번의 턴에서 visited로 중복 처리 해줘야 함!!!

 

 

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

1. 그래프 이동 : 한 번의 턴 이후에 그래프 이동해줘야 하므로 q.size 구한 후에 반복문 이후에 그래프 이동!
2. visited 중복 처리 

 

 

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

public class Main {
    static char[][] graph;
    //인접한 한 칸 또는 대각성 이동+움직이지 않을 수도 있음 !!
    static int[] dx = {0,1,-1,0,0,1,1,-1,-1};
    static int[] dy = {0,0,0,1,-1,1,-1,1,-1};
    static void chageGraph(){
        for(int i=7;i>=0;i--){
            for(int j=0;j<8;j++){
                if(i==7 && graph[i][j]=='#'){
                    graph[i][j]='.';
                } else if(graph[i][j]=='#'){
                    graph[i][j]='.';
                    graph[i+1][j]='#';
                }
            }
        }
    }

    static boolean bfs(int x, int y){
        Queue<int[]> q = new LinkedList<>();
        q.add(new int[]{x,y,0});

        while(!q.isEmpty()){
            int size = q.size();
            boolean[][] visited = new boolean[8][8]; //한 턴에서 같은 위치 중복 제거

            for(int k=0;k<size;k++){
                int[] now = q.poll();
                int nowX = now[0];
                int nowY = now[1];
                int nowC = now[2];

                if(graph[nowX][nowY]=='#'){
                    continue;
                }

                if(nowX==0&&nowY==7){
                    return true;
                }

                for(int i=0;i<9;i++){
                    int nextX = nowX+dx[i];
                    int nextY = nowY+dy[i];
                    if(nextX<0||nextX>=8||nextY<0||nextY>=8) continue;
                    if(visited[nextX][nextY]) continue;

                    if(graph[nextX][nextY]!='#'){
                        q.add(new int[]{nextX, nextY, nowC+1});
                        visited[nextX][nextY] = true;
                    }
                }
            }

            chageGraph();

        }
        return false;
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        graph = new char[8][8];

        for(int i=0;i<8;i++){
            String arr = br.readLine();
            for(int j=0;j<8;j++){
                graph[i][j] = arr.charAt(j);
            }
        }

        boolean success = bfs(7,0);

        if(success) System.out.println(1);
        else System.out.println(0);

    }
}