67 삐약 : 백준 5427| 불 [바킹독 문제 풀이|BFS|JAVA]

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

 

package BKD_0x9_BFS;

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


public class BOJ_5427 {
    static char[][] building;
    static Queue<Pair> person;
    static Queue<Pair> fire;

    static int[] dx={1,-1,0,0};
    static int[] dy={0,0,1,-1};

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int t = Integer.parseInt(br.readLine());
        StringTokenizer st;

        while(t-->0){
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());
            building = new char[h][w];
            person = new LinkedList<>();
            fire = new LinkedList<>();

            for(int i=0;i<h;i++){
                String input = br.readLine();
                for(int j=0;j<w;j++){
                    if(input.charAt(j)=='@'){
                        person.offer(new Pair(i,j,0));
                    }
                    if (input.charAt(j) == '*') {
                        fire.offer(new Pair(i,j,0));
                    }
                    building[i][j] = input.charAt(j);
                }
            }
            System.out.println(escape(h,w));
        }
    }
    static String escape(int h,int w){
        while (true){
            int f_size = fire.size();
            int p_size = person.size();

            if(p_size==0){
                return "IMPOSSIBLE";
            }
            while (f_size-->0){
                Pair fire_location = fire.poll();


                for(int i=0;i<4;i++){
                    int nx = fire_location.x+dx[i];
                    int ny = fire_location.y+dy[i];

                    if(nx>=0 && ny>=0 && nx<h && ny<w && building[nx][ny]=='.'){
                        fire.add(new Pair(nx,ny,0));
                        building[nx][ny]='*';
                    };
                }
            }

            while(p_size-->0){
                Pair person_location = person.poll();

                for(int i=0;i<4;i++){
                    int nx = person_location.x+dx[i];
                    int ny = person_location.y+dy[i];

                    if(nx<0 || ny<0 || nx>=h || ny>=w){
                        return Integer.toString(person_location.time+1);
                    }

                    if(nx>=0 && ny>=0 && nx<h && ny<w && building[nx][ny]=='.'){
                        person.add(new Pair(nx,ny,person_location.time+1));
                        building[nx][ny]='#';
                    };
                }
            }
        }
    }
    static class Pair{
        int x;
        int y;
        int time;
        public Pair(int x, int y, int time){
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }
}

 

 

오오오옹~ bfs 두개로 해야겠네에에 하고 진행한 문제풀이이다

불이 번지는 큐와 사람이 이동하는 큐를 따로 선언 후 불이 번지는 경로를 먼저 파악 후 사람이 이동을 하도록 하였다.

반복문은 현재 큐에 들어있는 개수만큼 따로 반복을 진행하였다.

좌표값을 저장하는 Pair 클래스레 소요되는 시간까지 카운팅하여 반환하도록 구현하였다.