๐Ÿ”ฅ ๋ฐฑ์ค€ 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)์ด ๊ฐ€์žฅ์ž๋ฆฌ์— ๋„๋‹ฌํ•˜๋ฉด ํƒˆ์ถœ ์„ฑ๊ณต!


**๐Ÿ’ก ๋” ๋‚˜์€ ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค๋ฉด ๋Œ“๊ธ€

ํƒœ๊ทธ: , , , , , , , ,

์นดํ…Œ๊ณ ๋ฆฌ: ,

์—…๋ฐ์ดํŠธ:

๋Œ“๊ธ€๋‚จ๊ธฐ๊ธฐ