๐Ÿ”ฅ ๋ฐฑ์ค€ 5472๋ฒˆ ๋ถˆ! (BFS ํ’€์ด ๋ฐ ์˜ค๋ฅ˜ ๋ถ„์„)

์—…๋ฐ์ดํŠธ:
3 ๋ถ„ ์†Œ์š”

๐Ÿ”ฅ ๋ฐฑ์ค€ 5472๋ฒˆ - ๋ถˆ! (BFS ํ’€์ด ๋ฐ ์˜ค๋ฅ˜ ๋ถ„์„)

๋ฐฑ์ค€ ๋กœ๊ณ 


๐Ÿ“Œ 1. ๋ฌธ์ œ ์„ค๋ช…

์ƒ๊ทผ(@)์ด๊ฐ€ ๋ถˆ(*)์ด ๋ฒˆ์ง€๋Š” ๊ฑด๋ฌผ์—์„œ ํƒˆ์ถœํ•˜๋Š” ๋ฌธ์ œ์ž…๋‹ˆ๋‹ค.
๋ถˆ(*)์€ ๋™์‹œ์— ํผ์ง€๊ณ , ์ƒ๊ทผ(@)์ด๋Š” ํ•œ ์นธ์”ฉ ์ด๋™ํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.
๋ฒฝ(#)์€ ์ด๋™ํ•  ์ˆ˜ ์—†๊ณ , ์ƒ๊ทผ์ด๊ฐ€ ๊ฑด๋ฌผ์˜ ๊ฐ€์žฅ์ž๋ฆฌ์— ๋„๋‹ฌํ•˜๋ฉด ํƒˆ์ถœํ•  ์ˆ˜ ์žˆ์Šต๋‹ˆ๋‹ค.

alt alt


๐Ÿ“Œ 2. ์ž…๋ ฅ ๋ฐ ์ถœ๋ ฅ ์˜ˆ์‹œ

๐Ÿ”น ์ž…๋ ฅ ์˜ˆ์‹œ

3
4 3
####
#*@#
####
7 6
###.###
#*#.#*#
#.....#
#.....#
#..@..#
#######
7 4
###.###
#*#.#*#
#.....#
####@##

๐Ÿ”น ์ถœ๋ ฅ ์˜ˆ์‹œ

IMPOSSIBLE
5
IMPOSSIBLE

๐Ÿ“Œ ์„ค๋ช…

  • @(์ƒ๊ทผ)๋Š” ์ด๋™ํ•˜๋ฉด์„œ ํƒˆ์ถœ์„ ์‹œ๋„
  • *(๋ถˆ)์€ ๋™์‹œ์— ํ™•์‚ฐ๋˜๋ฉฐ ์ƒ๊ทผ์˜ ์ด๋™์„ ๋ฐฉํ•ด
  • ํƒˆ์ถœ์ด ๊ฐ€๋Šฅํ•˜๋ฉด ์ตœ์†Œ ์‹œ๊ฐ„ ์ถœ๋ ฅ, ๋ถˆ๊ฐ€๋Šฅํ•˜๋ฉด โ€œIMPOSSIBLEโ€ ์ถœ๋ ฅ

๐Ÿ“Œ 3. ํ•ด๊ฒฐ ๋ฐฉ๋ฒ• (BFS)

์ด ๋ฌธ์ œ๋Š” ์ตœ๋‹จ ๊ฒฝ๋กœ ํƒ์ƒ‰ ๋ฌธ์ œ์ด๋ฏ€๋กœ,
BFS(๋„ˆ๋น„ ์šฐ์„  ํƒ์ƒ‰, Breadth-First Search)๋ฅผ ์‚ฌ์šฉํ•ด์•ผ ํ•ฉ๋‹ˆ๋‹ค.

๐Ÿ”น ํ•ต์‹ฌ ๋กœ์ง

  1. ๋ถˆ(*)๊ณผ ์ƒ๊ทผ(@)์„ ๊ฐ๊ฐ BFS ํ์— ์ €์žฅ
  2. ๋ถˆ(*)์ด ๋จผ์ € ํ™•์‚ฐ, ๊ทธ ํ›„ ์ƒ๊ทผ(@)์ด ์ด๋™
  3. ์ƒ๊ทผ(@)์ด ๊ฑด๋ฌผ์˜ ๊ฐ€์žฅ์ž๋ฆฌ์— ๋„๋‹ฌํ•˜๋ฉด ์ฆ‰์‹œ ํƒˆ์ถœ
  4. ์ƒ๊ทผ(@)์ด ์ด๋™ํ•  ๊ณณ์ด ์—†์œผ๋ฉด โ€œIMPOSSIBLEโ€ ์ถœ๋ ฅ

๐Ÿ“Œ 4. ์˜ค๋ฅ˜ ๋ถ„์„ ๋ฐ ํ•ด๊ฒฐ

๐Ÿ”น ์˜ค๋ฅ˜ 1: ์ž˜๋ชป๋œ ๋ฐฐ์—ด ๋ฒ”์œ„ ๊ฒ€์‚ฌ

if (nx < 0 || ny < 0 || nx >= width || ny >= height) {
    continue;
}

โœ… ๋ฌธ์ œ์ :

  • nx์™€ ny๋Š” ํ–‰(row), ์—ด(column)์„ ๋‚˜ํƒ€๋ƒ„
  • ์˜ฌ๋ฐ”๋ฅธ ๋ฒ”์œ„ ๊ฒ€์‚ฌ๋Š” nx >= height / ny >= width๊ฐ€ ๋˜์–ด์•ผ ํ•จ

โœ… ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•:

if (nx < 0 || ny < 0 || nx >= height || ny >= width) {
    continue;
}

๐Ÿ”น ์˜ค๋ฅ˜ 2: BFS์—์„œ sangQ.poll()์„ ํ•œ ๋ฒˆ๋งŒ ํ˜ธ์ถœํ•˜๋Š” ๋ฌธ์ œ

Point sang = sangQ.poll();

โœ… ๋ฌธ์ œ์ :

  • ํ˜„์žฌ ์ฝ”๋“œ์—์„œ๋Š” sangQ.poll()์ด ํ•œ ๋ฒˆ๋งŒ ํ˜ธ์ถœ๋˜๋ฏ€๋กœ, ํ•œ ๋ฒˆ์˜ BFS ๋ฃจํ”„์—์„œ ์ƒ๊ทผ(@)์ด ํ•œ ์นธ์”ฉ๋งŒ ์ด๋™ํ•จ
  • ๋ฐ˜๋ฉด ๋ถˆ(*)์€ ์—ฌ๋Ÿฌ ๊ฐœ๊ฐ€ ๋™์‹œ์— ํ™•์‚ฐํ•˜๋ฏ€๋กœ, ์ƒ๊ทผ์ด๊ฐ€ ๋ถˆ์„ ํ”ผํ•˜์ง€ ๋ชปํ•˜๋Š” ๋ฌธ์ œ๊ฐ€ ๋ฐœ์ƒ

โœ… ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•:
๐Ÿš€ BFS์˜ โ€œ๋ ˆ๋ฒจ ๋‹จ์œ„โ€๋กœ ์ด๋™ํ•˜๋„๋ก sangSize ์ ์šฉ

int sangSize = sangQ.size();
for (int s = 0; s < sangSize; s++) {
    Point sang = sangQ.poll();
    // ์ด๋™ ์ฒ˜๋ฆฌ
}

๐Ÿ”น ์˜ค๋ฅ˜ 3: visited ์ขŒํ‘œ ์ฒด๊ณ„ ์˜ค๋ฅ˜

if (map[nextY][nextX] == '.' && visited[nextY][nextX] == 0) {

โœ… ๋ฌธ์ œ์ :

  • ๋ฐฐ์—ด ์ขŒํ‘œ ์ฒด๊ณ„(map[nextY][nextX])์—์„œ nextX์™€ nextY๊ฐ€ ๋ฐ˜๋Œ€๋กœ ๋“ค์–ด๊ฐ
  • map[y][x] ํ˜•ํƒœ๋กœ ์ ‘๊ทผํ•ด์•ผ ํ•จ

โœ… ํ•ด๊ฒฐ ๋ฐฉ๋ฒ•:
๐Ÿš€ ์˜ฌ๋ฐ”๋ฅธ ์ขŒํ‘œ ์ฒด๊ณ„ ์ ์šฉ

if (map[nextRow][nextCol] == '.' && visited[nextRow][nextCol] == 0) {

๐Ÿ“Œ 5. ์ˆ˜์ •๋œ ์ฝ”๋“œ

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

public class Back_5472 {

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

    static int[] dX = {0, 0, 1, -1}; // ์ด๋™ ๋ฐฉํ–ฅ (์ขŒ์šฐ)
    static int[] dY = {1, -1, 0, 0}; // ์ด๋™ ๋ฐฉํ–ฅ (์ƒํ•˜)

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

        int T = Integer.parseInt(br.readLine());

        StringTokenizer st;
        for (int i = 0; i < T; i++) {
            st = new StringTokenizer(br.readLine());
            int w = Integer.parseInt(st.nextToken());
            int h = Integer.parseInt(st.nextToken());

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

            Queue<Point> fires = new LinkedList<>();
            Queue<Point> sang = new LinkedList<>();

            for (int j = 0; j < h; j++) {
                String temp = br.readLine();
                for (int k = 0; k < w; k++) {
                    map[j][k] = temp.charAt(k);

                    if (map[j][k] == '*') {
                        fires.offer(new Point(j, k, 0));
                    } else if (map[j][k] == '@') {
                        sang.offer(new Point(j, k, 0));
                    }
                }
            }
            int result = bfs(w, h, map, sang, fires);
            System.out.println(result == -1 ? "IMPOSSIBLE" : result);
        }
    }

    private static int bfs(int width, int height, char[][] map, Queue<Point> sangQ, Queue<Point> fires) {
        int[][] visited = new int[height][width];

        while (!sangQ.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 >= height || ny >= width) {
                        continue;
                    }

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

            // ๐Ÿƒโ€โ™‚๏ธ ์ƒ๊ทผ ์ด๋™ (๋ ˆ๋ฒจ BFS)
            int sangSize = sangQ.size();
            for (int s = 0; s < sangSize; s++) {
                Point sang = sangQ.poll();
                for (int i = 0; i < 4; i++) {
                    int nextRow = sang.x + dX[i];
                    int nextCol = sang.y + dY[i];

                    if (nextRow < 0 || nextCol < 0 || nextRow >= height || nextCol >= width) {
                        return sang.time + 1;
                    }

                    if (map[nextRow][nextCol] == '.' && visited[nextRow][nextCol] == 0) {
                        visited[nextRow][nextCol] = 1;
                        sangQ.offer(new Point(nextRow, nextCol, sang.time + 1));
                    }
                }
            }
        }
        return -1;
    }
}

๐Ÿ’ก ๋” ๋‚˜์€ ๋ฐฉ๋ฒ•์ด ์žˆ๋‹ค๋ฉด ๋Œ“๊ธ€๋กœ ๊ณต์œ ํ•ด์ฃผ์„ธ์š”! ๐Ÿ˜Š

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

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

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

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