๐Ÿงฑ ๋ฐฑ์ค€ 2206๋ฒˆ ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ (BFS ํ’€์ด)

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

๐Ÿงฑ ๋ฐฑ์ค€ 2206๋ฒˆ - ๋ฒฝ ๋ถ€์ˆ˜๊ณ  ์ด๋™ํ•˜๊ธฐ (BFS ํ’€์ด)

๋ฐฑ์ค€ ๋กœ๊ณ 


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

Nร—M ํฌ๊ธฐ์˜ ๋ฐฐ์—ด์ด ์ฃผ์–ด์ง€๊ณ ,
๋ฒฝ(1)์ด ์žˆ๋Š” ๊ฒฝ์šฐ ํ•œ ๊ฐœ์˜ ๋ฒฝ์„ ๋ถ€์ˆ˜๊ณ  ์ง€๋‚˜๊ฐˆ ์ˆ˜ ์žˆ๋‹ค.
์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋กœ ๋„์ฐฉ์  (N-1, M-1)๊นŒ์ง€ ์ด๋™ํ•ด์•ผ ํ•œ๋‹ค.

alt alt


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

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

6 4
0100
1110
1000
0000
0111
0000

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

15

๐Ÿ“Œ ์„ค๋ช…

  • (0,0)์—์„œ (5,3)๊นŒ์ง€ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋กœ ์ด๋™
  • ๋ฒฝ์„ ํ•œ ๋ฒˆ ๋ถ€์ˆ˜๋Š” ๊ฒฝ์šฐ ๋” ๋น ๋ฅธ ๊ฒฝ๋กœ ๊ฐ€๋Šฅ

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

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

๐Ÿ”น BFS๋ฅผ ์‚ฌ์šฉํ•ด์•ผ ํ•˜๋Š” ์ด์œ 

  • ๋ชจ๋“  ์นธ์„ ํ•œ ๋ฒˆ์”ฉ ๋ฐฉ๋ฌธํ•˜๋Š” ๊ฒฝ์šฐ O(Nร—M)
  • DFS(๊นŠ์ด ์šฐ์„  ํƒ์ƒ‰)๋ณด๋‹ค BFS๊ฐ€ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ํƒ์ƒ‰์— ์ ํ•ฉ
  • BFS๋ฅผ ํ™œ์šฉํ•˜์—ฌ ๋ฒฝ์„ ํ•œ ๋ฒˆ๋งŒ ๋ถ€์ˆ  ์ˆ˜ ์žˆ๋„๋ก ๊ด€๋ฆฌ

๐Ÿ“Œ 4. ํ•ต์‹ฌ ์ฝ”๋“œ ๋ถ„์„

static class Point {
    int x, y, count;
    boolean destroyed; // ๋ฒฝ์„ ๋ถ€์‰ˆ๋Š”์ง€ ์—ฌ๋ถ€

    public Point(int x, int y, int count, boolean destroyed) {
        this.x = x;
        this.y = y;
        this.count = count;
        this.destroyed = destroyed;
    }
}

โœ… Point ํด๋ž˜์Šค

  • x, y โ†’ ํ˜„์žฌ ์ขŒํ‘œ
  • count โ†’ ์ด๋™ ๊ฑฐ๋ฆฌ (์ตœ๋‹จ ๊ฑฐ๋ฆฌ)
  • destroyed โ†’ ๋ฒฝ์„ ๋ถ€์‰ˆ๋Š”์ง€ ์—ฌ๋ถ€ (true = ๋ถ€์ˆจ)

๐Ÿ”น visited 3์ฐจ์› ๋ฐฐ์—ด (๋ฒฝ์„ ๋ถ€์ˆœ ๊ฒฝ์šฐ vs ๋ถ€์ˆ˜์ง€ ์•Š์€ ๊ฒฝ์šฐ)

boolean[][][] visited = new boolean[N][M][2];

โœ… visited[N][M][0] โ†’ ๋ฒฝ์„ ๋ถ€์ˆ˜์ง€ ์•Š๊ณ  ๋ฐฉ๋ฌธํ•œ ๊ฒฝ์šฐ
โœ… visited[N][M][1] โ†’ ๋ฒฝ์„ ๋ถ€์ˆœ ํ›„ ๋ฐฉ๋ฌธํ•œ ๊ฒฝ์šฐ
โœ… ๊ฐ™์€ ์œ„์น˜๋ฅผ ๋ฒฝ์„ ๋ถ€์ˆœ ์ƒํƒœ/๋ถ€์ˆ˜์ง€ ์•Š์€ ์ƒํƒœ๋กœ ๋ฐฉ๋ฌธํ•  ์ˆ˜ ์žˆ์œผ๋ฏ€๋กœ 3์ฐจ์› ๋ฐฐ์—ด์„ ์‚ฌ์šฉ


๐Ÿ”น BFS ํƒ์ƒ‰ ๊ณผ์ •

Queue<Point> points = new LinkedList<>();
points.offer(new Point(0, 0, 1, false));
visited[0][0][0] = true;

โœ… BFS๋ฅผ ์œ„ํ•œ ํ ์ดˆ๊ธฐํ™”

  • (0,0)์—์„œ ์‹œ์ž‘ (count=1)
  • ์ฒ˜์Œ์—๋Š” ๋ฒฝ์„ ๋ถ€์ˆ˜์ง€ ์•Š์€ ์ƒํƒœ (destroyed=false)

๐Ÿ”น BFS ํƒ์ƒ‰ (๋ฒฝ ๋ถ€์ˆ˜๊ธฐ ๋กœ์ง ํฌํ•จ)

for (int i = 0; i < 4; i++) {
    int dirX = now.x + dX[i];
    int dirY = now.y + dY[i];

    if (dirX >= N || dirX < 0 || dirY >= M || dirY < 0) continue;

    // ์ด๋™ ๊ฐ€๋Šฅ (๋นˆ ๊ณต๊ฐ„)
    if (map[dirX][dirY] == '0') {
        if (!now.destroyed && !visited[dirX][dirY][0]) {
            points.offer(new Point(dirX, dirY, now.count + 1, false));
            visited[dirX][dirY][0] = true;
        } else if (now.destroyed && !visited[dirX][dirY][1]) {
            points.offer(new Point(dirX, dirY, now.count + 1, true));
            visited[dirX][dirY][1] = true;
        }
    }

    // ๋ฒฝ ๋ถ€์ˆ˜๊ธฐ (๋ฒฝ์„ ํ•œ ๋ฒˆ๋„ ๋ถ€์ˆ˜์ง€ ์•Š์€ ๊ฒฝ์šฐ)
    else if (map[dirX][dirY] == '1') {
        if (!now.destroyed) {
            points.offer(new Point(dirX, dirY, now.count + 1, true));
            visited[dirX][dirY][1] = true;
        }
    }
}

โœ… ์ด๋™ํ•  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ

  • ๋นˆ ๊ณต๊ฐ„(0)์ผ ๋•Œ โ†’ ๋ฒฝ์„ ๋ถ€์ˆœ ์—ฌ๋ถ€์— ๋”ฐ๋ผ ๋ฐฉ๋ฌธ ์ฒดํฌ
  • ๋ฒฝ(1)์„ ๋ถ€์ˆ  ์ˆ˜ ์žˆ๋Š” ๊ฒฝ์šฐ โ†’ ํ•œ ๋ฒˆ๋งŒ ๋ถ€์ˆ˜๋„๋ก ์„ค์ •

๐Ÿ”น ๋ชฉํ‘œ ์ง€์  ๋„์ฐฉ ์—ฌ๋ถ€ ํ™•์ธ

if (now.x == N - 1 && now.y == M - 1) {
    return now.count;
}

โœ… ๋„์ฐฉํ•˜๋ฉด ์ฆ‰์‹œ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ ๋ฐ˜ํ™˜
โœ… BFS๋Š” ์ตœ๋‹จ ๊ฑฐ๋ฆฌ๋ฅผ ๋ณด์žฅํ•˜๋ฏ€๋กœ, ์ฒซ ๋ฒˆ์งธ ๋„์ฐฉํ•œ ๊ฒฝ๋กœ๊ฐ€ ํ•ญ์ƒ ์ตœ๋‹จ ๊ฑฐ๋ฆฌ


๐Ÿ“Œ 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_2206 {

    static class Point {
        int x, y, count;
        boolean destroyed;

        public Point(int x, int y, int count, boolean destroyed) {
            this.x = x;
            this.y = y;
            this.count = count;
            this.destroyed = destroyed;
        }
    }

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

    static int N, M;

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());

        char[][] map = new char[N][M];

        for (int i = 0; i < N; i++) {
            String temp = br.readLine();
            for (int j = 0; j < M; j++) {
                map[i][j] = temp.charAt(j);
            }
        }
        System.out.println(bfs(map));
    }

     private static int bfs(char[][] map) {
        Queue<Point> points = new LinkedList<>();
        points.offer(new Point(0, 0, 1, false));
        boolean[][][] visited = new boolean[N][M][2];

        visited[0][0][0] = true;
        while (!points.isEmpty()) {
            Point now = points.poll();

            if (now.x == N - 1 && now.y == M - 1) {
                return now.count;
            }

            for (int i = 0; i < 4; i++) {
                int dirX = now.x + dX[i];
                int dirY = now.y + dY[i];

                if (dirX >= N || dirX < 0 || dirY >= M || dirY < 0) continue;

                if (map[dirX][dirY] == '0') {
                    if (!now.destroyed && !visited[dirX][dirY][0]) {
                        points.offer(new Point(dirX, dirY, now.count + 1, false));
                        visited[dirX][dirY][0] = true;
                    } else if (now.destroyed && !visited[dirX][dirY][1]) {
                        points.offer(new Point(dirX, dirY, now.count + 1, true));
                        visited[dirX][dirY][1] = true;
                    }
                } else if (map[dirX][dirY] == '1') {
                    if (!now.destroyed) {
                        points.offer(new Point(dirX, dirY, now.count + 1, true));
                        visited[dirX][dirY][1] = true;
                    }
                }
            }
        }

        return -1;
    }
}

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

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

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

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