[백준 2178번] 미로탐색 - BFS

백준 2178번 기본적인 BFS 문제이다.

 

일단 문제를 확인하게 되면, 

(1, 1)에서 (N, M)까지의 배열상태를 나타내는 int형 배열이 주어지고 (1, 1)에서 시작해서 (N, M)까지 가는데 가장 최소의 길로 갈 때, 지나쳐 온 칸의 수를 세어주는 문제이다.
여기서 조건이 주어지는 것은 미로에서 1인 칸만 이동할 수 있고 0인 칸은 이동할 수 없다는 것이다.

 

일단 알고리즘을 풀 때, BFS로 풀게되는 경우는 최소라는 단어가 들어갔으면 BFS로 접근하여 풀이법을 생각합니다.

보통 그렇더라구요...

 

이 문제는 기본적인 BFS문제이기 때문에 풀이법은 보통의 BFS 풀이하는 방법과 동일합니다.

추가되는 것은 지나쳐 온 칸의 수를 카운트하기 위해 별도의 배열을 하나 더 두는 것 밖에 없습니다.

 

우선 소스코드 먼저 살펴볼게요.

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

public class BAEKJOON2178 {
    static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};
    static int[][] pathCount;
    static int[][] map;

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

        int N, M;

        String[] input = br.readLine().split(" ");
        N = Integer.parseInt(input[0]);
        M = Integer.parseInt(input[1]);

        map = new int[N+1][M+1];
        pathCount = new int[N+1][M+1];
        pathCount[1][1] = 1;

        for(int i = 0; i < N; i++) {
            input = br.readLine().split("");
            for(int j = 0; j < M; j++) {
                map[i+1][j+1] = Integer.parseInt(input[j]);
            }
        }

        bfs(N, M);
    }

    static void bfs(int N, int M) {
        Queue<Dot> queue= new LinkedList<>();
        boolean[][] visited = new boolean[N+1][M+1];

        Dot startDot = new Dot(1, 1);
        queue.offer(startDot);

        visited[1][1] = true;

        while (!queue.isEmpty()) {
            Dot tempDot = queue.poll();

            for(int i = 0; i < 4; i++) {
                Dot destDot = new Dot(tempDot.x + dir[i][1], tempDot.y + dir[i][0]);

                if (destDot.x < 1 || destDot.x > M || destDot.y < 1 || destDot.y > N) { continue; }
                if (visited[destDot.y][destDot.x] || map[destDot.y][destDot.x] == 0) { continue; }

                queue.offer(destDot);
                visited[destDot.y][destDot.x] = true;
                pathCount[destDot.y][destDot.x] = pathCount[tempDot.y][tempDot.x] + 1;
            }
        }

        System.out.println(pathCount[N][M]);
    }
}

class Dot {
    int x, y;

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

 

BFS에서 기본적으로 Queue을 활용한다는 점에 주목하시면 좋을 것 같아요. 

그렇기 때문에, Java에서는 Queue 인터페이스를 구현하는 LinkedList을 활용했어요.

 

우선 탐색을 위해 먼저 선언해야할 것이 있어요.

// 4방향으로만 이동할 수 있기 때문에, 방향을 나타내는 dir
static int[][] dir = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}};

// 지나쳐온 칸의 수를 카운트하기 위한 2차원 배열
static int[][] pathCount;

// 미로를 나타내는 2차원 배열
static int[][] map;

 

이렇게 선언을 한 후, BFS의 풀이와 동일하게 하면 될 것 같아요.

 

1️⃣ 시작점 (1, 1)을 Queue에 넣는다. 넣으면서 탐색했음을 vitisted을 true로 바꿔주는건 필수겠죠?

 

2️⃣Queue의 값이 없을 때까지 무한 반복을 돌린다.

 

3️⃣Queue의 값을 꺼내와서 각 방향으로 탐색하면서 배열의 범위를 벗어나진 않는지, 이미 방문한 칸인지를 확인하면 될 것 같아요. (각 방향은 아까 dir 이차원 배열 선언한거 기억하시죠?)

 

4️⃣범위에 벗어나지 않고 방문하지 않은 칸이면 Queue에 넣어주고 방문했음을 표시하고 현재 칸까지 오는데 걸린 수에 +1을 해서 도착지점에 초기화를 시켜줍니다.

 

이런식으로 무한루프를 돌려주면 모든 점을 탐색하고 결국 (N, M)에 도착하는 거리가 최소의 칸이 되게 됩니다.

 

가장 간단한 BFS 문제였습니다.