[백준] 4179 불!, Go/Java

0. 들어가면서

불! 문제이다.
시작점이 여러가지인 문제이다.
BFS문제이다.

1. Java

1.1 내가 푼 코드

package bj.ch09_bfs;

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

public class BJ_4179_불_01 {
    /*
     * r*c = 1000000 이므로 대략 NlogN안에 끝내야 한다.
     * 지훈, 불 각각의 큐를 사용한다.
     * 지훈이는 불이 난 곳으로 이동할 수 없기 때문에 불 먼저 돌린다.
     * 지훈이는 거리까지 알아야한다.
     * 4 4
     * ####
     * #JF#
     * #..#
     * #..#
     */
    static Queue<int[]> fQ = new LinkedList<>();
    static Queue<int[]> jQ = new LinkedList<>();
    static char[][] map;
    static int[][] dist;
    static int R, C;

    static int[] dy = { -1, 1, 0, 0 }; // 상하좌우
    static int[] dx = { 0, 0, -1, 1 };

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        dist = new int[R][C];

        for (int y = 0; y < R; y++) {
            String line = br.readLine();
            for (int x = 0; x < C; x++) {
                char c = line.charAt(x);
                map[y][x] = c;
                dist[y][x] = -1;
                if (c == 'J') {
                    jQ.offer(new int[] { y, x });
                    dist[y][x] = 0;
                }
                if (c == 'F') {
                    fQ.offer(new int[] { y, x });
                }
            }
        }

        while (!jQ.isEmpty()) {
            // 불 먼저 돌린다.
            int fSize = fQ.size();
            for (int fs = 0; fs < fSize; fs++) {
                int[] curF = fQ.poll();
                for (int d = 0; d < 4; d++) {
                    int nFy = curF[0] + dy[d];
                    int nFx = curF[1] + dx[d];
                    if (nIR(nFy, R) || nIR(nFx, C)) // 범위 초과
                        continue;
                    if (map[nFy][nFx] == '#') // 벽
                        continue;
                    if (map[nFy][nFx] == 'F') // 이미 불
                        continue;
                    map[nFy][nFx] = 'F'; // 불이 번져
                    fQ.offer(new int[] { nFy, nFx });
                }
            }
            // 지훈이 차례
            int jSize = jQ.size();
            for (int js = 0; js < jSize; js++) {
                int[] curJ = jQ.poll();
                for (int d = 0; d < 4; d++) {
                    int nJy = curJ[0] + dy[d];
                    int nJx = curJ[1] + dx[d];
                    if (nIR(nJy, R) || nIR(nJx, C)) { // 범위 초과
                        System.out.println(dist[curJ[0]][curJ[1]] + 1);
                        return;
                    }
                    if (map[nJy][nJx] == '#') { // 벽
                        continue;
                    }
                    if (map[nJy][nJx] == 'F') { // 불
                        continue;
                    }
                    if (dist[nJy][nJx] >= 0) { // 이미 방문
                        continue;
                    }
                    dist[nJy][nJx] = dist[curJ[0]][curJ[1]] + 1;
                    jQ.offer(new int[] { nJy, nJx });
                }
            }
        }
        System.out.println("IMPOSSIBLE");
    }

    private static boolean nIR(int v, int range) {
        return (v < 0 || v >= range) ? true : false;
    }
}

1.3 바킹독을 참고한 코드

package bj.ch09_bfs;

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

public class BJ_4179_불_01_BarkingDog {
    /*
     * r*c = 1000000 이므로 대략 NlogN안에 끝내야 한다.
     * 지훈, 불 각각의 큐를 사용한다.
     * 지훈이는 불이 난 곳으로 이동할 수 없기 때문에 불 먼저 돌린다.
     * 지훈이는 거리까지 알아야한다.
     * 4 4
     * ####
     * #JF#
     * #..#
     * #..#
     */
    static Queue<int[]> fQ = new LinkedList<>();
    static Queue<int[]> jQ = new LinkedList<>();
    static char[][] map;
    static int[][] distF;
    static int[][] distJ;
    static int R, C;

    static int[] dy = { -1, 1, 0, 0 }; // 상하좌우
    static int[] dx = { 0, 0, -1, 1 };

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        distF = new int[R][C];
        distJ = new int[R][C];

        for (int y = 0; y < R; y++) {
            String line = br.readLine();
            for (int x = 0; x < C; x++) {
                char c = line.charAt(x);
                map[y][x] = c;
                distF[y][x] = -1;
                distJ[y][x] = -1;
                if (c == 'J') {
                    jQ.offer(new int[] { y, x });
                    distJ[y][x] = 0;
                }
                if (c == 'F') {
                    fQ.offer(new int[] { y, x });
                    distJ[y][x] = 0;
                }
            }
        }

        while (!fQ.isEmpty()) {
            int[] curF = fQ.poll();
            for (int d = 0; d < 4; d++) {
                int nFy = curF[0] + dy[d];
                int nFx = curF[1] + dx[d];
                if (nIR(nFy, R) || nIR(nFx, C)) // 범위 초과
                    continue;
                if (map[nFy][nFx] == '#' || distF[nFy][nFx] >= 0) // 벽 이거나 불이 번졌거나
                    continue;
                distF[nFy][nFx] = distF[curF[0]][curF[1]] + 1;
                fQ.offer(new int[] { nFy, nFx });
            }
        }
        // 불 다 번졌고 얼마만에 번지는지도 계산이 끝난 상태
        // 즉, 지훈이는 불이 번지는 시간을 알고있다.
        // 지훈이는 불이 번지는 시간보다 빨리 도착해야한다.
        while (!jQ.isEmpty()) {
            int[] curJ = jQ.poll();
            for (int d = 0; d < 4; d++) {
                int nJy = curJ[0] + dy[d];
                int nJx = curJ[1] + dx[d];
                if (nIR(nJy, R) || nIR(nJx, C)) { // 범위 초과, 즉 탈출이다!
                    System.out.println(distJ[curJ[0]][curJ[1]] + 1);
                    return;
                }
                if (map[nJy][nJx] == '#' || distJ[nJy][nJx] >= 0) // 벽 이거나 이미 방문했거나
                    continue;
                if (distF[nJy][nJx] != -1 && distF[nJy][nJx] <= distJ[curJ[0]][curJ[1]] + 1) // 불이 번지는 시간이 지훈이가 도착하는
                                                                                             // 시간보다 빠르면
                    continue;
                distJ[nJy][nJx] = distJ[curJ[0]][curJ[1]] + 1;
                jQ.offer(new int[] { nJy, nJx });
            }
        }
        System.out.println("IMPOSSIBLE"); // 탈출 불가능
    }

    private static boolean nIR(int v, int range) {
        return (v < 0 || v >= range) ? true : false;
    }
}

1.4 해설

• 시작점이 여러개이고, 거리를 구해야하는 문제이다.
• 불을 먼저 퍼뜨리고, 지훈이를 퍼뜨린다.
• 이 과정에서 불필요한 변수를 줄일 수 있지 않을까?
• 좀 더 빨리 반복문을 빠져나올 수 있지 않을까에 대해서 생각해보았다.
• 바킹독
  • 방문이나, 거리에대한 dist를 써주고, 반복문안에 반복문을 없앴다.
  • 나는 불번지고 지훈이 가고 불번지고 지훈이 가고 이런식으로 했는데
  • 바킹독은 불 모두 번지고 시간 기록하고
  • 지훈이 모두 이동하고 시간 기록하고 이런식으로 했다.

2. Go

CLOSING

재활훈련 필요, 멀었다.