*BFS(너비 우선 탐색)* 목수의 미로 탈출

이번 문제는 BFS 문제이다.

https://kimtaesoo99.tistory.com/85

너비 우선 탐색(BFS)

위의 글에서 맨 마지막에 나오는 미로 찾기의 심화 문제이다.

 

핵심

이 문제는 생각을 달리해야 한다. S 부분에서 E부분까지 이동하는데, 벽으로 막힌 경우도 있다. 따라서 우리는 S에서 시작하여 끝까지 가는 것만이 아닌, S에서 시작하는 경우와 E에서 시작하는 경우 모두 생각한 뒤 벽에 도달하는 거리도 생각해주어야 한다.

즉 아래의 그림과 같이 벽도 최단거리를 구해야 한다. 

이를 B도 적용해 준다.

 

정답 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
    static int n;
    static int m;
    static int[][] map;
    static int[][] startA;
    static int[][] startB;
    static int[] dx = {1, 0, -1, 0};
    static int[] dy = {0, 1, 0, -1};
    static boolean isHasWall = false;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        m = sc.nextInt();
        map = new int[n][m];
        startA = new int[n][m];
        startB = new int[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                map[i][j] = sc.nextInt();
                if (map[i][j] ==1) isHasWall = true;
            }
        }
        startBfsOfA(n - 1, 0);
        startBfsOfB(0, m - 1);
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                if (map[i][j] == 1&& startA[i][j]!=0 && startB[i][j]!=0){
                    min = Math.min(min, startA[i][j] + startB[i][j]);
                }
            }
        }
        if (isHasWall)
            System.out.println(min);
        else System.out.println(startA[0][m-1]);

    }

    static void startBfsOfA(int y, int x) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{y, x});
        startA[y][x] = 0;

        while (!queue.isEmpty()) {
            int[] next = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextY = next[0] + dy[i];
                int nextX = next[1] + dx[i];

                if (0 <= nextY && nextY < n && 0 <= nextX && nextX < m) {
                    if (startA[nextY][nextX] == 0 && map[nextY][nextX] == 0) {
                        queue.add(new int[]{nextY, nextX});
                        startA[nextY][nextX] = startA[next[0]][next[1]] + 1;
                    } else if (startA[nextY][nextX] == 0 && map[nextY][nextX] == 1) {
                        startA[nextY][nextX] = startA[next[0]][next[1]] + 1;
                    }
                }
            }
        }
    }

    static void startBfsOfB(int y, int x) {
        Queue<int[]> queue = new LinkedList<>();
        queue.offer(new int[]{y, x});
        startB[y][x] = 0;

        while (!queue.isEmpty()) {
            int[] next = queue.poll();

            for (int i = 0; i < 4; i++) {
                int nextY = next[0] + dy[i];
                int nextX = next[1] + dx[i];

                if (0 <= nextY && nextY < n && 0 <= nextX && nextX < m) {
                    if (startB[nextY][nextX] == 0 && map[nextY][nextX] == 0) {
                        queue.add(new int[]{nextY, nextX});
                        startB[nextY][nextX] = startB[next[0]][next[1]] + 1;
                    } else if (startB[nextY][nextX] == 0 && map[nextY][nextX] == 1) {
                        startB[nextY][nextX] = startB[next[0]][next[1]] + 1;
                    }
                }
            }
        }
    }
}

해설

우선 코드가 길기 때문에 전체적인 흐름을 먼저 보면, 값을 입력받을 때 벽이 있는지를 먼저 확인한다.

만약 벽이 없는 경우는 단순하게 BFS 한 값으로 최단 경로를 찾을 수 있다.

하지만 벽이 있는 경우는 단순하지 않다.

위의 그림처럼 BFS로 탐색을 하는데, 벽에도 최단거리 값을 넣어준다. 하지만 queue에는 벽의 위치를 넣지 않는다.

이동은 길로만 하기 때문이다.

이러한 과정을 B도 진행하면, 각각 A에서 시작한 BFS값이 담겨있는 맵과 B에서 시작한 BFS값이 담겨있는 맵이 생성된다.

이제 원래 기존에 있던 지도를 비교하여, 원래 벽이었던 곳이면서, 우리가 만든 맵의 값이 0이 아니라면

두 값을 더한 뒤 최소 거리와 비교하여 업데이트해 준다.

여기서 우리가 만든 맵의 값이 0 이 아닌지 확인해준 이유는 0이라는 이유는 벽이 2개 이상으로 막혀있기 때문에,

값을 업데이트조차 못했다는 의미이기  때문이다.

 

 

 

배운 점

단순하게 문제만 보았을 때, 감이 전혀 잡히지 않았다.

벽을 부수는 경우가 있기 때문에 boolean타입으로 부순경우를 생각하고 진행하려 했다.

이러한 알고리즘은 생각보다 쉽지 않았고, 이해하는데도 더욱 복잡하다고 느껴졌다.

문제에 적힌 대로 단순하게 시작점으로부터만 값을 구하려 하니 막막했지만, 생각을 달리하니 창의력도 성장하는 느낌이다.

문제를 있는 그대로 풀기보단 영리하게 푸는 습관을 갖도록 연습해야겠다.