πŸ”₯ λ°±μ€€ 4179번 뢈! (BFS 풀이)

μ—…λ°μ΄νŠΈ:
3 λΆ„ μ†Œμš”

πŸ”₯ λ°±μ€€ 4179번 - 뢈! (BFS 풀이)

λ°±μ€€ 둜고


πŸ“Œ 1. 문제 μ„€λͺ…

μ§€ν›ˆ(J)이가 뢈(F)이 λ‚œ λ―Έλ‘œμ—μ„œ νƒˆμΆœν•˜λŠ” λ¬Έμ œμž…λ‹ˆλ‹€.
뢈(F)은 λ™μ‹œμ— 퍼지고, μ§€ν›ˆ(J)μ΄λŠ” ν•œ μΉΈμ”© 이동할 수 μžˆμŠ΅λ‹ˆλ‹€.
λ²½(#)은 이동할 수 μ—†κ³ , μ§€ν›ˆμ΄κ°€ 미둜의 κ°€μž₯μžλ¦¬μ— λ„λ‹¬ν•˜λ©΄ νƒˆμΆœν•  수 μžˆμŠ΅λ‹ˆλ‹€.

alt


πŸ“Œ 2. μž…λ ₯ 및 좜λ ₯ μ˜ˆμ‹œ

πŸ”Ή μž…λ ₯ μ˜ˆμ‹œ

4 4
####
#JF#
#..#
#..#

πŸ”Ή 좜λ ₯ μ˜ˆμ‹œ

3

πŸ“Œ μ„€λͺ…

  • J(μ§€ν›ˆ)λŠ” (1,2)μ—μ„œ μ‹œμž‘
  • F(뢈)λŠ” (1,1)μ—μ„œ μ‹œμž‘
  • λΆˆμ€ λ™μ‹œμ— ν™•μ‚°λ˜κ³ , μ§€ν›ˆμ΄λŠ” λΆˆλ³΄λ‹€ λ¨Όμ € λ„μ°©ν•˜λ©΄ νƒˆμΆœ κ°€λŠ₯

πŸ“Œ 3. ν•΄κ²° 방법 (BFS)

이 λ¬Έμ œλŠ” μ΅œλ‹¨ 경둜 탐색 λ¬Έμ œμ΄λ―€λ‘œ,
BFS(λ„ˆλΉ„ μš°μ„  탐색, Breadth-First Search)λ₯Ό μ‚¬μš©ν•΄μ•Ό ν•©λ‹ˆλ‹€.

πŸ”Ή 핡심 둜직

  1. 뢈(F)κ³Ό μ§€ν›ˆ(J)을 각각 BFS 큐에 μ €μž₯
  2. 뢈(F)이 λ¨Όμ € ν™•μ‚°, κ·Έ ν›„ μ§€ν›ˆ(J)이 이동
  3. μ§€ν›ˆ(J)이 미둜의 κ°€μž₯μžλ¦¬μ— λ„λ‹¬ν•˜λ©΄ μ¦‰μ‹œ νƒˆμΆœ
  4. μ§€ν›ˆ(J)이 이동할 곳이 μ—†μœΌλ©΄ β€œIMPOSSIBLE” 좜λ ₯

πŸ“Œ 4. Java μ½”λ“œ (BFS)

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

public class Back_4179 {

    static int dX[] = {0, 0, 1, -1};
    static int dY[] = {1, -1, 0, 0};

    static int R, C;

    static class Point {
        int x, y, time;

        Point(int x, int y, int time) {
            this.x = x;
            this.y = y;
            this.time = time;
        }
    }

    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());

        char[][] map = new char[R][C];
        Queue<Point> fires = new LinkedList<>();
        Queue<Point> jihos = new LinkedList<>();

        for (int i = 0; i < R; i++) {
            String temp = br.readLine();
            for (int j = 0; j < C; j++) {
                map[i][j] = temp.charAt(j);
                if (map[i][j] == 'F') {
                    fires.offer(new Point(i, j, 0)); // 뢈 μœ„μΉ˜ μ €μž₯
                } else if (map[i][j] == 'J') {
                    jihos.offer(new Point(i, j, 0)); // μ§€ν›ˆ μœ„μΉ˜ μ €μž₯
                }
            }
        }

        int result = bfs(map, jihos, fires);
        System.out.println(result == -1 ? "IMPOSSIBLE" : result);
    }

    private static int bfs(char[][] map, Queue<Point> jihos, Queue<Point> fires) {
        int[][] visited = new int[R][C];

        while (!jihos.isEmpty()) {
            // πŸ”₯ 뢈 ν™•μ‚°
            int fireSize = fires.size();
            for (int f = 0; f < fireSize; f++) {
                Point fire = fires.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = fire.x + dX[i];
                    int ny = fire.y + dY[i];

                    if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
                        continue;
                    }

                    if (map[nx][ny] == '.' || map[nx][ny] == 'J') {
                        map[nx][ny] = 'F';
                        fires.offer(new Point(nx, ny, fire.time + 1));
                    }
                }
            }

            // πŸƒβ€β™‚οΈ μ§€ν›ˆ 이동
            int jihoSize = jihos.size();
            for (int j = 0; j < jihoSize; j++) {
                Point jiho = jihos.poll();
                for (int i = 0; i < 4; i++) {
                    int nx = jiho.x + dX[i];
                    int ny = jiho.y + dY[i];

                    // βœ… κ°€μž₯μžλ¦¬μ— λ„λ‹¬ν•˜λ©΄ νƒˆμΆœ
                    if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
                        return jiho.time + 1;
                    }

                    if (map[nx][ny] == '.' && visited[nx][ny] == 0) {
                        visited[nx][ny] = 1;
                        jihos.offer(new Point(nx, ny, jiho.time + 1));
                    }
                }
            }
        }
        return -1;
    }
}

πŸ“Œ 5. 핡심 μ½”λ“œ μ„€λͺ…

1️⃣ fires 큐λ₯Ό μ‚¬μš©ν•˜μ—¬ 뢈(F) ν™•μ‚°

int fireSize = fires.size();
for (int f = 0; f < fireSize; f++) {
    Point fire = fires.poll();
    for (int i = 0; i < 4; i++) {
        int nx = fire.x + dX[i];
        int ny = fire.y + dY[i];

        if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
            continue;
        }

        if (map[nx][ny] == '.' || map[nx][ny] == 'J') {
            map[nx][ny] = 'F';
            fires.offer(new Point(nx, ny, fire.time + 1));
        }
    }
}

βœ… ν•œ 번의 BFS λ‹¨κ³„μ—μ„œ λͺ¨λ“  λΆˆμ„ ν™•μ‚°μ‹œν‚΄
βœ… 뢈(F)이 λ¨Όμ € μ΄λ™ν•˜λ„λ‘ ν•˜μ—¬ μ§€ν›ˆ(J)의 이동을 λ°©ν•΄ν•˜λ„λ‘ μ„€μ •


2️⃣ jihos 큐λ₯Ό μ‚¬μš©ν•˜μ—¬ μ§€ν›ˆ(J) 이동

int jihoSize = jihos.size();
for (int j = 0; j < jihoSize; j++) {
    Point jiho = jihos.poll();
    for (int i = 0; i < 4; i++) {
        int nx = jiho.x + dX[i];
        int ny = jiho.y + dY[i];

        if (nx < 0 || ny < 0 || nx >= R || ny >= C) {
            return jiho.time + 1;
        }

        if (map[nx][ny] == '.' && visited[nx][ny] == 0) {
            visited[nx][ny] = 1;
            jihos.offer(new Point(nx, ny, jiho.time + 1));
        }
    }
}

βœ… λΆˆλ³΄λ‹€ λ¨Όμ € λ„μ°©ν•˜λ©΄ νƒˆμΆœ 성곡!
βœ… 뢈(F)κ³Ό μ§€ν›ˆ(J)이 같은 μ‹œκ°„λŒ€μ— ν™•μ‚°λ˜λŠ” ꡬ쑰


πŸ“Œ 6. κ²°λ‘ 

βœ… BFSλ₯Ό ν™œμš©ν•˜μ—¬ μ΅œλ‹¨ μ‹œκ°„μœΌλ‘œ νƒˆμΆœ 경둜λ₯Ό 찾음
βœ… 뢈(F)이 λ¨Όμ € ν™•μ‚°λ˜λ„λ‘ ν•˜μ—¬, μ§€ν›ˆ(J)이 μ§€λ‚˜κ°ˆ 길을 λ§‰μŒ
βœ… μ§€ν›ˆ(J)이 κ°€μž₯μžλ¦¬μ— λ„λ‹¬ν•˜λ©΄ νƒˆμΆœ 성곡!


**πŸ’‘ 더 λ‚˜μ€ 방법이 μžˆλ‹€λ©΄ λŒ“κΈ€

νƒœκ·Έ: , , , , , , , ,

μΉ΄ν…Œκ³ λ¦¬:

μ—…λ°μ΄νŠΈ:

λŒ“κΈ€λ‚¨κΈ°κΈ°