[문제풀이] 백준 5427 불

 

 

🛎️ 문제 

 

📢 틀린 이유

불이 퍼지는 간격과 상근이가 움직이는 간격이 같으려면 BFS를 돌릴 때 불이 갈 곳을 탐색하고 que에 넣는 depth와 상근이가 이동하는 depth가 같아야 한다.

그 부분을 구현하지 못해서 계속 모든 문제가 "IMPOSSIBLE"이 나왔다.

 

😀 제대로 된 코드

제대로 문제를 풀려면 불을 넣는 큐 사이즈만큼만 다음 좌표를 탐색하고 상근이도 상근이의 큐 사이즈만큼만 다음 좌표를 탐색하고 이동시켜주어 둘이 움직이는 간격을 맞춰줘야 한다.

주요 코드

 while (!sangQ.isEmpty()){
    int firesize = fireQ.size();
    int sangsize = sangQ.size();
    
    for (int i = 0; i < firesize; i++){
        ... 생략 ...
    }

    for (int i = 0; i < sangsize; i++){
    	... 생략 ...
    }

⚠️ for문에 큐의 size를 넣어줄 때 자주하는 실수가 있는데..

반복문 범위에 바로 que.size() 로 넣어주면 반복문이 실행되면서 동적으로 변화한다. 따라서 필요한 횟수만큼 반복되지 않기 때문에 변수에 대입하여 주어야 한다. 자주 틀ㄹ림...ㅠ

 

그 외 로직 오류

1. 출구 판별 조건문

if (cr == 0 || cc == 0 || cr == h-1 || cc == w-1) { // 출구 판별
    System.out.println(sang[2]);
    return;
}

이 부분을 사방탐색 for 문 안에 작성해두어서 아래와 같은 반례가 존재했다.

.@
..

output 2
answer 1

 

 

전체 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main { // BOJ_5427_불

    static int[] dr = {-1, 1, 0, 0};
    static int[] dc = {0, 0, -1, 1};
    static char[][] map;
    static boolean[][] visited;
    static ArrayDeque<int[]> sangQ;
    static ArrayDeque<int[]> fireQ;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int T = Integer.parseInt(br.readLine());
        for (int tc =0; tc<T; tc++){
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken()); // 지도 너비 c
            int h = Integer.parseInt(st.nextToken()); // 지도 높이 r

            map = new char[h][w];
            visited = new boolean[h][w];

            sangQ = new ArrayDeque<>();
            fireQ = new ArrayDeque<>();

            for (int i = 0; i < h; i++){
                String str = br.readLine();
                for (int j = 0; j < w; j++){
                    char ch = str.charAt(j);
                    if (ch == '@'){
                        sangQ.add(new int[] {i, j, 1});
                    }
                    if (ch == '*'){
                        fireQ.add(new int[] {i, j});
                    }
                    map[i][j] = ch;
                }
            } // map end

            bfs(h, w);
        }
    }

    private static void bfs(int h, int w){
        while (!sangQ.isEmpty()){
            int firesize = fireQ.size();
            int sangsize = sangQ.size();
            for (int i = 0; i < firesize; i++){
                int[] fire = fireQ.poll();

                for (int d = 0; d < 4; d++){
                    int nr = fire[0] + dr[d];
                    int nc = fire[1] + dc[d];

                    if (nr < 0 || nc < 0 || nr >= h || nc >= w || map[nr][nc] == '#' || map[nr][nc] == '*') continue;

                    fireQ.add(new int[] {nr, nc});
                    map[nr][nc] = '*';
                }
            }

            for (int i = 0; i < sangsize; i++){
                int[] sang = sangQ.poll();
                int cr = sang[0];
                int cc = sang[1];
                if (cr == 0 || cc == 0 || cr == h-1 || cc == w-1) { // 출구 판별
                    System.out.println(sang[2]);
                    return;
                }
                for (int d = 0; d < 4; d++){
                    int nr = sang[0] + dr[d];
                    int nc = sang[1] + dc[d];

                    if (nr < 0 || nc < 0 || nr >= h || nc >= w || map[nr][nc] != '.' || visited[nr][nc]) continue;
                    sangQ.add(new int[] {nr, nc, sang[2]+1});
                    visited[nr][nc] = true;
                }
            }
        }
        System.out.println("IMPOSSIBLE");
    }
}