(JAVA) [BOJ]백준 4179번, 불

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

4179번: 불!

 

4179, 불!

📌 난이도 : Gold 4

📌 알고리즘 : DFS & BFS

📌 자료구조 : Queue

 

간만에 코테를 준비하다보니 많이 해맸었다. DFS & BFS 와 Queue 를 사용하여 문제를 해결했다.

 

🧩 프로세스

📚 초기화 및 선언

: 불과 진수의 이동에 대한 정보를 가져야 한다. 해당 좌표까지 걸리는 시간을 담을 distF, distJ 와 좌표들을 담을 Queue 2개를 미리 선언해준다. 주어진 좌표를 탐색하며 거리 배열(dist) 을 -1로 초기화 해주고 해당 좌표만 0으로 초기화 해준다. 또한 Queue에 x, y 좌표를 담아야 하기에 int[][] 로 처리할 수도 있지만 직관적으로 보기 위해 클래스를 하나 생성해준다.

class Node {
    int X, Y;
    Node(int x, int y) {
        this.X = x;
        this.Y = y;
    }
}

static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringBuilder sb = new StringBuilder();
static StringTokenizer st;
static int R,C;
static char[][] map;
static int[][] distF, distJ;
static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
static Queue<Node> QF = new LinkedList<>(); // 불의 좌표
static Queue<Node> QJ = new LinkedList<>(); // 지훈이 좌표

public static void main(String[] args) throws IOException{
    input();
    process();
}

static void input() throws IOException {
    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 i=0; i<R; i++) {
        String str = br.readLine();
        for(int j=0; j<C; j++) {
            map[i][j] = str.charAt(j);
            distF[i][j] = -1;// 불의 전파 시간
            distJ[i][j] = -1; // 지훈이의 이동 시간

            // 불좌표
            if(map[i][j] == 'F') {
                QF.offer(new Node(i, j));
                distF[i][j] = 0;
            }
            // 지훈이 좌표
            if(map[i][j] == 'J') {
                QJ.offer(new Node(i, j));
                distJ[i][j] = 0;
            }

        }
    }
}

 

📚 탐색

1. 불의 좌표가 담겨진 QF 먼저 탐색한다. 범위를 벗어나지 않고, 벽이 아니며 이미 지나가지 않은 구간들을 차례로 탐색하며 거리 값을 갱신한다. 

 

2. 진수의 탐색에는 고려할 사항이 있다. 해당 좌표에 도달했을 때 불의 시간이 더 작은 경우는 해당 좌표에 불이 더 빠르게 도착했다는 의미이다. 이 경우에 진수는 해당 좌표를 지나갈 수 없다. 해당 부분에 대한 예외처리를 진행할 때 불이 지나가지 않은 경우도 잘 고려해 주어야 한다. 더 자세한 설명은 주석에 첨부해 두었다.

while (!QF.isEmpty()) {
    Node cur = QF.poll();

    for(int k=0; k<4; k++) {
        int nx = cur.X + dir[k][0];
        int ny = cur.Y + dir[k][1];

        if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
        if(distF[nx][ny] >= 0 || map[nx][ny] == '#') continue; // 불이 지나갔거나 벽은 예외처리

        distF[nx][ny] = distF[cur.X][cur.Y] + 1; // 거리 갱신, 현재 좌표에서 + 1
        QF.offer(new Node(nx, ny)); // 큐 갱신
    }
}

while (!QJ.isEmpty()) {
    Node cur = QJ.poll();

    for(int k=0; k<4; k++) {
        int nx = cur.X + dir[k][0];
        int ny = cur.Y + dir[k][1];

        // 지역을 벗어난 경우, 탈출
        if(nx < 0 || ny < 0 || nx >= R || ny >= C) {
            System.out.println(distJ[cur.X][cur.Y] + 1);
            return;
        }

        // 지나갔거나 벽은 예외처리
        if(distJ[nx][ny] >= 0 || map[nx][ny] == '#') continue;

        // 불의 시간이 더 작은 경우는 해당 좌표에 더 빠르게 도착했단 의미, 예외처리
        // 불이 지나가지 않은 것도 감안해야 한다.
        if(distF[nx][ny] != -1 && (distF[nx][ny] <= distJ[cur.X][cur.Y] + 1)) continue;

        distJ[nx][ny] = distJ[cur.X][cur.Y] + 1; // 거리 갱신
        QJ.offer(new Node(nx, ny)); // 큐 갱신
    }
}

System.out.println("IMPOSSIBLE");

 

✅ 전체 코드

: 스프링 & JPA 를 공부하느라 간만에 코딩테스트를 공부했더니 많이 까먹어서 시간 소요가 길었다. 한 문제씩이라도 매일매일 꾸준히 풀어야 함을 상기할 수 있는 하루다 : )

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

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;
    static int R,C;
    static char[][] map;
    static int[][] distF, distJ;
    static int[][] dir = {{1,0},{-1,0},{0,1},{0,-1}};
    static Queue<Node> QF = new LinkedList<>(); // 불의 좌표
    static Queue<Node> QJ = new LinkedList<>(); // 지훈이 좌표
    
    public static void main(String[] args) throws IOException{
        input();
        process();
    }

    static void input() throws IOException {
        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 i=0; i<R; i++) {
            String str = br.readLine();
            for(int j=0; j<C; j++) {
                map[i][j] = str.charAt(j);
                distF[i][j] = -1;// 불의 전파 시간
                distJ[i][j] = -1; // 지훈이의 이동 시간

                // 불좌표
                if(map[i][j] == 'F') {
                    QF.offer(new Node(i, j));
                    distF[i][j] = 0;
                }
                // 지훈이 좌표
                if(map[i][j] == 'J') {
                    QJ.offer(new Node(i, j));
                    distJ[i][j] = 0;
                }

            }
        }
    }

    static void process() {
        while (!QF.isEmpty()) {
            Node cur = QF.poll();

            for(int k=0; k<4; k++) {
                int nx = cur.X + dir[k][0];
                int ny = cur.Y + dir[k][1];

                if(nx < 0 || ny < 0 || nx >= R || ny >= C) continue;
                if(distF[nx][ny] >= 0 || map[nx][ny] == '#') continue; // 불이 지나갔거나 벽은 예외처리

                distF[nx][ny] = distF[cur.X][cur.Y] + 1; // 거리 갱신, 현재 좌표에서 + 1
                QF.offer(new Node(nx, ny)); // 큐 갱신
            }
        }

        while (!QJ.isEmpty()) {
            Node cur = QJ.poll();

            for(int k=0; k<4; k++) {
                int nx = cur.X + dir[k][0];
                int ny = cur.Y + dir[k][1];

                // 지역을 벗어난 경우, 탈출
                if(nx < 0 || ny < 0 || nx >= R || ny >= C) {
                    System.out.println(distJ[cur.X][cur.Y] + 1);
                    return;
                }

                // 지나갔거나 벽은 예외처리
                if(distJ[nx][ny] >= 0 || map[nx][ny] == '#') continue;

                // 불의 시간이 더 작은 경우는 해당 좌표에 더 빠르게 도착했단 의미, 예외처리
                // 불이 지나가지 않은 것도 감안해야 한다.
                if(distF[nx][ny] != -1 && (distF[nx][ny] <= distJ[cur.X][cur.Y] + 1)) continue;

                distJ[nx][ny] = distJ[cur.X][cur.Y] + 1; // 거리 갱신
                QJ.offer(new Node(nx, ny)); // 큐 갱신
            }
        }

        System.out.println("IMPOSSIBLE");
    }
}

class Node {
    int X, Y;
    Node(int x, int y) {
        this.X = x;
        this.Y = y;
    }
}