섹션 8 DFS, BFS - 11. 미로의 최단거리 통로(BFS)

제 설명

7×7 크기의 격자 미로에서 (1,1)에서 시작해 (7,7)에 도착하는 최단 경로의 길이를 구하는 문제입니다.
여기서 경로의 길이는 출발점에서 도착점까지 지나간 칸의 수를 의미합니다.

• 이동 가능한 칸: 0 (도로)
• 이동 불가능한 칸: 1 (벽)
• 상하좌우 4방향으로만 이동 가능

입력 & 출력

입력

• 7×7 격자판의 각 칸의 값 (0 또는 1)

출력

• 최단 경로의 길이 출력
• 도착할 수 없으면 -1 출력

예시

입력:
0 0 0 0 0 0 0
0 1 1 1 1 1 0
0 0 0 1 0 0 0
1 1 0 1 0 1 1
1 1 0 1 0 0 0
1 0 0 0 1 0 0
1 0 1 0 0 0 0

출력:
12

해결 방법

• 이 문제는 최단 거리를 구하는 것이기 때문에, DFS보다 BFS가 적합합니다.
• BFS는 현재 위치에서 갈 수 있는 모든 방향을 먼저 탐색하고, 점차 퍼져나가면서 도착점까지의 최소 이동 횟수를 구합니다.
• 각 칸까지의 이동 횟수를 별도의 dis 배열에 저장해 사용합니다.

코드 구현

package partDfsBfs;

import java.util.*;

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

public class Problem11 {
    static int[] dx = {-1, 0, 1, 0};
    static int[] dy = {0, 1, 0, -1};
    static int[][] board, dis;

    public void BFS(int x, int y) {
        Queue<Point> q = new LinkedList<>();
        q.offer(new Point(x, y));
        board[x][y] = 1; // 방문 표시

        while (!q.isEmpty()) {
            Point tmp = q.poll();
            for (int i = 0; i < 4; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                if (1 <= nx && nx <= 7 && 1 <= ny && ny <= 7 && board[nx][ny] == 0) {
                    board[nx][ny] = 1;
                    q.offer(new Point(nx, ny));
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1;
                }
            }
        }
    }

    public static void main(String[] args) {
        Problem11 T = new Problem11();
        Scanner kb = new Scanner(System.in);
        board = new int[8][8];
        dis = new int[8][8];

        for (int i = 1; i <= 7; i++) {
            for (int j = 1; j <= 7; j++) {
                board[i][j] = kb.nextInt();
            }
        }

        T.BFS(1, 1);

        if (dis[7][7] == 0) System.out.println(-1);
        else System.out.println(dis[7][7]);
        
        kb.close();
    }
}

코드 설명

• Point 클래스: 현재 위치 좌표를 큐에 저장할 때 사용
• board: 입력으로 주어진 미로 정보
• dis: 각 위치까지의 최단 거리 저장 배열
• board[nx][ny] = 1: 이미 방문했음을 표시하여 중복 탐색 방지
• dis[nx][ny] = dis[tmp.x][tmp.y] + 1: 이전 칸 거리 + 1 저장

시간 복잡도

• BFS는 각 칸을 최대 한 번씩만 방문하므로
  O(N²) (여기선 N=7)
  → 총 49칸이므로 완전탐색이 가능