백준 4179 불! (Java,자바)

jonghyukLee·2022년 10월 31일
0

이번에 풀어본 문제는
백준 4179번 불! 입니다.

📕 문제 링크

❗️코드

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

class Location {
    int x, y;
    int time;

    public Location(int x, int y, int time) {
        this.x = x;
        this.y = y;
        this.time = time;
    }
}
public class Main {
    static int R,C;
    static char [][] map;
    static int [][] burnedTime;
    static boolean [][] isVisited;
    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));
        StringTokenizer st = new StringTokenizer(br.readLine());
        R = Integer.parseInt(st.nextToken());
        C = Integer.parseInt(st.nextToken());

        map = new char[R][C];
        isVisited = new boolean[R][C];
        burnedTime = new int[R][C];
        Queue<Location> q = new LinkedList<>();
        //초기화
        Location jh = new Location(0,0,0);
        Location fire = new Location(0,0,0);

        for (int i = 0; i < R; i++) {
            String tmpInput = br.readLine();
            for (int j = 0; j < C; j++) {
                char c = tmpInput.charAt(j);
                if (c == 'J') {
                    jh = new Location(i, j, 0);
                    isVisited[i][j] = true;
                }
                else if (c == 'F') {
                    q.add(new Location(i, j, 0));
                    burnedTime[i][j] = 1; //어차피 못가므로 1로 처리
                }
                map[i][j] = c;
            }
        }
        // fire 먼저 이동
        q.add(fire);
        while(!q.isEmpty()) {
            Location cur = q.poll();
            int nextTime = cur.time + 1;

            for (int idx = 0; idx < 4; idx++) {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if (isValid(mx, my) && map[mx][my] == '.' && burnedTime[mx][my] < 1) {
                    burnedTime[mx][my] = nextTime;
                    q.add(new Location(mx, my, nextTime));
                }
            }
        }

        // 지훈이 이동
        int answer = Integer.MAX_VALUE;
        q.add(jh);
        while(!q.isEmpty()) {
            Location cur = q.poll();
            int nextTime = cur.time + 1;
            // 탈출 성공
            if (isEdge(cur.x, cur.y)) {
                answer = Math.min(answer, nextTime);
                continue;
            }

            for (int idx = 0; idx < 4; idx++) {
                int mx = cur.x + dx[idx];
                int my = cur.y + dy[idx];

                if (isValid(mx, my) && !isVisited[mx][my] && map[mx][my] == '.') {
                    // 불이 없거나, 나중에 타거나
                    if (burnedTime[mx][my] < 1 || burnedTime[mx][my] > nextTime) {
                        isVisited[mx][my] = true;
                        q.add(new Location(mx, my, nextTime));
                    }
                }
            }
        }
        System.out.print(answer != Integer.MAX_VALUE ? answer : "IMPOSSIBLE");
    }
    static boolean isValid(int x, int y) {
        return x >= 0 && y >= 0 && x < R && y < C;
    }
    static boolean isEdge(int x, int y) {
        return x == 0 || y == 0 || x == R - 1 || y == C - 1;
    }
}

📝 풀이

지훈이가 불에 타지 않고 탈출할 수 있다면 몇 분걸린지를 출력하고, 할수없다면 IMPOSSIBLE을 출력하는 문제입니다.
지훈이를 이동시키기 전에, 각 인덱스에 불이 몇분에 퍼지는지를 기록해두기 위해 불을 먼저 퍼뜨립니다.
이후 지훈이가 이동할 때, 불이 없거나, 지훈이가 도달하는 시점보다 뒤에 불이 붙는다면, 이동할 수 있다고 판단할 수 있게 됩니다.
위 과정을 통해 맵에 가장자리에 지훈이가 도달하게 된다면, 카운트의 +1 값을 정답에 누적시켜주면 해결할 수 있습니다.

📜 후기

입력값으로 불이 여러개 들어올 수도 있다는 점을 고려하지 못해서, 몇 번틀렸습니다 ㅠ 아직도 문제를 꼼꼼히 못읽네요..

profile
머무르지 않기!

0개의 댓글