[백준/JAVA] 4179번: 불!

🔺 문제

4179번: 불!

 

 

🔺 코드

import java.util.*;
import java.io.*;
 
public class Main {
    static int[] dx = {0,0,-1,1};
    static int[] dy = {1,-1,0,0};
    
    static int R, C, res;
    static char[][] map;
    static Queue<State> fire, jh;
    
    static class State {
        int x, y, d;
        
        public State(int x, int y, int d) {
            this.x = x;
            this.y = y;
            this.d = d;
        }
    }
    
    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];
        
        jh = new LinkedList<>();
        fire = new LinkedList<>();
        
        // 입력받아 배열 초기화
        for(int i = 0 ; i < R ; i++) {
            map[i] = br.readLine().toCharArray();
            for(int j = 0 ; j < C ; j++) {
                // 불 위치
                if(map[i][j] == 'F') {
                    fire.add(new State(i, j, 0));
                }
                // 지훈 위치
                if(map[i][j] == 'J') {
                    jh.add(new State(i, j, 0));
                }
            }
        }       
        
        System.out.println(bfs() ? res : "IMPOSSIBLE");
    }
    
    private static boolean bfs() {
        while(!jh.isEmpty()) {
            // 1. 불이 먼저 퍼짐
            int size = fire.size();
            for(int i = 0 ; i < size ; i++) {
                State now = fire.poll();
                
                for(int d = 0 ; d < 4 ; d++) {
                    int xx = now.x + dx[d];
                    int yy = now.y + dy[d];
                    
                    if(xx < 0 || xx >= R || yy < 0 || yy >= C) continue;
                    if(map[xx][yy] == '#' || map[xx][yy] == 'F') continue;
                    
                    map[xx][yy] = 'F';
                    fire.add(new State(xx, yy, now.d + 1));                    
                }
            }
            
            
            // 2. 지훈이가 불을 피해 이동
            size = jh.size();
            for(int i = 0 ; i < size ; i++) {
                State now = jh.poll();
                
                for(int d = 0 ; d < 4 ; d++) {
                    int xx = now.x + dx[d];
                    int yy = now.y + dy[d];
                    
                    // 💥 범위 벗어남 = 탈출 💥
                    if(xx < 0 || yy < 0 || xx >= R || yy >= C) {
                        res = now.d + 1;
                        return true;
                    }
                    
                    if(map[xx][yy] == '#' || map[xx][yy] == 'F' || map[xx][yy] == 'J')  continue;
                    
                    map[xx][yy] = 'J';
                    jh.add(new State(xx, yy, now.d + 1));
                }
            }
        }
        return false;
    }
}
 

✅ 해결 아이디어
✔ BFS
1. 지훈 & 불 위치 저장
2. 불 위치 퍼뜨림 (범위 벗어나거나 / 벽이거나 / 이미 방문한 경우, pass)
3. 불이 퍼지고 지훈 이동. → 가장자리면(=범위 벗어나면) 탈출 성공. (벽이거나 / 불이거나 / 이미 방문한 곳이면, pass)

 

💥 유의사항

• 불을 먼저 퍼뜨리고, 지훈이를 이동시켜야 함 (불에 탈 수 있는 위치에 지훈이가 있으면 안 되니까)

 

---

🔺 다른 풀이들

- 헐 내가 생각하던 풀이다!!

https://www.acmicpc.net/source/62966594

로그인

https://www.acmicpc.net/source/43888742

로그인

---

💬 느낀 점

다음에 풀라고 하면 풀 수 있을 것 같다!! (아마도.. 아마데우스..)

 

 

1회독	2회독	3회독	4회독	5회독
V

---

(참고)

[BOJ] 4179.불(BFS).java

 

[백준] 4179: 불! (Java)