백준 : 4179

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

4179번: 불!

실수 하기 쉬운 것:
1. 불은 하나가 아니라 여러개 잇을 수가 있다.
2. BFS로 접근시 q에 넣을때는 불이 없는 지점이였지만 q에 빼서 다른곳으로 가는것을 처리할때 현재위치가 불인지 아닌지 한번더 check해야한다. 불이 있는곳에 사람이 있을수 없으니.
3. 이중 서치때 사람위치와 불의 위치들을 저장하고 사람먼저넣고 불을 넣으면 사람이 움직이고 불이 움직이는 시뮬레이션이 만들어진다.

package com.ssafy.algo;
 
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.LinkedList;
import java.util.Queue;
 
public class 불 {
    static int N, M;
    static char[][] map;
 
    static class Pair {
        int y;
        int x;
        char c;
 
        public Pair(int y, int x, char c) {
            super();
            this.y = y;
            this.x = x;
            this.c = c;
        }
    }
 
    static int dy[] = { 0, 0, -1, 1 };
    static int dx[] = { 1, -1, 0, 0 };
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
        String str[] = br.readLine().split(" ");
 
        N = Integer.parseInt(str[0]);
        M = Integer.parseInt(str[1]);
        Pair startJ = null;
 
        map = new char[N][M];
        ArrayList<Pair> startF = new ArrayList<>();
        for (int i = 0; i < N; i++) {
            map[i] = br.readLine().toCharArray();
            for (int j = 0; j < M; j++) {
                if (map[i][j] == 'J') {
                    startJ = new Pair(i, j, 'J');
                }
 
                if (map[i][j] == 'F') {
                    startF.add(new Pair(i, j, 'F'));
                }
            }
        }
 
        Queue<Pair> q = new LinkedList<>();
 
        q.add(startJ);
        for(int i=0;i<startF.size();i++) {
            q.add(startF.get(i));
        }
 
        int Answer = -1;
        int time = 0;
 
        while (!q.isEmpty()) {
            int size = q.size();
 
            for (int s = 0; s < size; s++) {
                Pair tmp = q.poll();
 
                if (tmp.c == 'J') {
                    if (tmp.y < 0 || tmp.x < 0 || tmp.y >= N || tmp.x >= M) {
                        Answer = time;
                        break;
                    } 
                    else if(map[tmp.y][tmp.x]=='F')continue;
                    else {
                        for (int d = 0; d < 4; d++) {
                            int ny = tmp.y + dy[d];
                            int nx = tmp.x + dx[d];
                            if (ny < 0 || nx < 0 || ny >= N || nx >= M) {
                                q.add(new Pair(ny,nx,'J'));
                            }else {
                                
                                if (map[ny][nx] != '.')
                                    continue;
                                map[ny][nx] = 'J';
                                q.add(new Pair(ny, nx, 'J'));
                            }
                            
                        }
                    }
                } else {
                    for (int d = 0; d < 4; d++) {
                        int ny = tmp.y + dy[d];
                        int nx = tmp.x + dx[d];
                        if (ny < 0 || nx < 0 || ny >= N || nx >= M)
                            continue;
                        if (map[ny][nx] == '#')
                            continue;
                        if (map[ny][nx] == 'F')
                            continue;
                        map[ny][nx] = 'F';
                        q.add(new Pair(ny, nx, 'F'));
                    }
 
                }
            }
            if (Answer != -1)
                break;
            time++;
 
        }
 
        if (Answer != -1) {
            System.out.println(Answer);
        } else {
            System.out.println("IMPOSSIBLE");
        }
    }
}