[BOJ] 4179 - 불!

개인적인 풀이일 뿐, 최적의 정답이 아님을 알려드립니다.

 

문제

www.acmicpc.net/problem/4179

4179번: 불!

난이도: 골드 4

사용언어: JAVA

 

풀이

전형적으로 BFS를 이용하는 문제입니다. 단지 보통 BFS를 수행하는 문제와 다른 점은 지훈이와 불의 이동을 따로 체크해주어야 한다는 점입니다. 그래서 저는 BFS를 위한 큐와 BFS 함수를 2개씩 만들어 지훈이의 이동과 불의 이동을 따로 관리했습니다. 

 

그 외에는 크게 고려해야 할 사항이 없는 문제입니다.

 

import java.io.*;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;
 
class Main {
 
    static int R, C;
    static char[][] arr;
    static int[][] d = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 이동할 수 있는 방향
    static int cnt = 0;
 
    static class position {
        int x;
        int y;
 
        public position(int x, int y) {
            this.x = x;
            this.y = y;
        }
    }
 
    public static void bfs_f(position p) { // 불의 이동을 위한 bfs 함수
        int i;
        int nx, ny;
        for (i = 0; i < 4; i++) {
            nx = p.x + d[i][0];
            ny = p.y + d[i][1];
            if (arr[nx][ny] != 0 && arr[nx][ny] != '#' && arr[nx][ny] != 'F') {
                arr[nx][ny] = 'F';
                q_f.add(new position(nx, ny));
            }
        }
    }
 
    public static void bfs_j(position p) { // 지훈이의 이동을 위한 bfs 함수
        int i;
        int nx, ny;
        for (i = 0; i < 4; i++) {
            nx = p.x + d[i][0];
            ny = p.y + d[i][1];
            if (arr[nx][ny] == '.') {
                arr[nx][ny] = 'J';
                q_j.add(new position(nx, ny));
            } else if (arr[nx][ny] == 0) { // 가장자리에 도착하면 탈출
                System.out.println(cnt + 1);
                System.exit(0);
            }
        }
    }
 
    static Queue<position> q_f = new LinkedList<>(); // 불의 이동을 관리하기 위한 큐
    static Queue<position> q_j = new LinkedList<>(); // 지훈이의 이동을 관리하기 위한 큐
 
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        String s;
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());
        arr = new char[R + 2][C + 2];
 
        for (int i = 1; i <= R; i++) {
            s = br.readLine();
            for (int j = 1; j <= C; j++) {
                arr[i][j] = s.charAt(j - 1);
                if (arr[i][j] == 'J') { // 지훈이의 초기 위치를 큐에 삽입
                    q_j.add(new position(i, j));
                } else if (arr[i][j] == 'F') { // 불의 초기 위치들을 큐에 삽입
                    q_f.add(new position(i, j));
                }
            }
        }
 
        int k;
        while (!q_j.isEmpty()) { // 지훈이가 더이상 움직일 공간이 없을 때 까지 반복
            k = q_f.size();
            for (int i = 0; i < k; i++) { // 불의 이동부터 체크
                bfs_f(q_f.poll());
            }
            k = q_j.size();
            for (int i = 0; i < k; i++) { // 지훈의 이동 체크
                bfs_j(q_j.poll());
            }
            cnt++;
        }
        bw.write("IMPOSSIBLE\n"); // 지훈이가 움직일 수 있는 공간이 없으므로 탈출 불가능
        bw.flush();
        bw.close();
        br.close();
    }
}