미로의 최단거리 통로(BFS)

7x7 격자판 미로를 탈출하는 최단경로의 길이를 구하는 문제를 해결하기 위해 BFS(너비 우선 탐색) 알고리즘을 사용한다. BFS는 출발점에서 도착점까지 도달할 수 있는 모든 경로를 '너비'로 확장해 나가며 최단 경로를 구하는 알고리즘이다.

 

문제 설명

격자판의 좌표 (1, 1)에서 출발하여 (7, 7)에 도착하는 최단 경로의 길이를 출력한다. 격자판의 각 칸은 벽(1) 또는 도로(0)로 이루어져 있으며, 이동할 수 있는 방향은 상, 하, 좌, 우로 한 칸씩 이동한다. 도착점에 도달할 수 없는 경우 -1을 출력한다.

위 미로에서 최단 경로는 총 12칸을 이동한 것이다.

 

예시 입력

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

 

BFS 알고리즘의 특징

BFS는 시작점에서 출발하여 같은 거리의 모든 좌표를 먼저 탐색한 후, 그다음으로 거리가 증가하는 좌표들을 차례대로 탐색한다. 즉, 너비를 우선으로 탐색하기 때문에 모든 가능한 경로를 균형 있게 고려할 수 있다.

 

BFS 탐색의 동작 원리

1. 출발점 (1, 1)에서 시작하여 상하좌우 네 방향을 모두 탐색한다.
2. 가능한 경로는 모두 큐에 넣고, 같은 거리에 있는 점을 모두 방문한 후 다음 단계로 넘어간다.
3. 이렇게 같은 거리의 좌표를 먼저 탐색하므로 최단 거리를 구할 수 있다.
4. 한 번 방문한 좌표는 다시 방문하지 않도록 체크한다.

BFS 탐색 흐름

1. Step 1: 시작점 (1, 1)에서 상하좌우로 탐색하여 갈 수 있는 좌표 (1, 2)와 (2, 1)을 큐에 넣는다.
2. Step 2: (1, 2)와 (2, 1)에서 다시 상하좌우로 탐색하여 다음으로 갈 수 있는 좌표들을 큐에 넣는다.
3. Step 3: 큐에서 꺼낸 좌표들을 탐색하여 도착점 (7, 7)까지 도달할 때까지 반복한다.

큐를 이용한 BFS 시각화

1. (1,1)에서 출발하여 상하좌우로 갈 수 있는 모든 경로를 큐에 넣는다.
2. 같은 거리의 모든 경로를 먼저 탐색하고, 그다음 거리로 확장해 나간다.
3. 도착점에 도달했을 때 최단 경로의 길이를 계산한다.

코드 구현

package com.example.codingtest;

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

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

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

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        board = new int[8][8]; // 1부터 7까지 사용하므로 8x8 배열 선언
        dis = new int[8][8]; // 거리 저장을 위한 배열

        // 입력받은 미로 데이터를 board 배열에 저장
        for (int i = 1; i <= 7; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= 7; j++) {
                board[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        // BFS 탐색 시작
        BFS(1, 1);

        // 도착점까지의 거리를 출력
        if (dis[7][7] == 0) {
            System.out.println(-1); // 도착할 수 없으면 -1 출력
        } else {
            System.out.println(dis[7][7]); // 도착점까지의 최단 거리 출력
        }
    }

    public static void BFS(int x, int y) {
        Queue<Point> queue = new LinkedList<>();
        queue.offer(new Point(x, y)); // 시작점 큐에 넣기
        board[x][y] = 1; // 방문 표시

        while (!queue.isEmpty()) {
            Point tmp = queue.poll(); // 큐에서 좌표 꺼내기
            for (int i = 0; i < 4; i++) {
                int nx = tmp.x + dx[i];
                int ny = tmp.y + dy[i];
                
                // 유효한 범위 내에서 이동할 수 있는 좌표인지 확인
                if (nx >= 1 && nx <= 7 && ny >= 1 && ny <= 7 && board[nx][ny] == 0) {
                    board[nx][ny] = 1; // 방문 표시
                    queue.offer(new Point(nx, ny)); // 큐에 새로운 좌표 추가
                    dis[nx][ny] = dis[tmp.x][tmp.y] + 1; // 이동 거리 기록
                }
            }
        }
    }
}

코드 설명

1. Point 클래스: 좌표를 저장하는 클래스이다. x, y 좌표를 관리한다.
2. board 배열: 미로의 상태를 저장한다. 1은 벽, 0은 도로를 나타낸다.
3. dis 배열: 각 좌표까지의 이동 거리를 저장하는 배열이다. 출발점에서 도착점까지의 최단 거리를 계산할 수 있다.
4. BFS 메서드: 큐를 이용해 미로를 탐색한다. 상하좌우로 이동할 수 있는 모든 좌표를 탐색하며, 방문한 좌표는 다시 방문하지 않도록 처리한다.

BFS의 장점

BFS는 너비 우선 탐색 방식이므로 가장 먼저 도착점에 도달하는 경로가 최단 경로가 된다. 탐색을 할 때 한 번에 한 단계씩 이동하므로 경로의 길이를 정확하게 측정할 수 있다.

 

결론

BFS 알고리즘을 활용하면 7x7 미로에서 출발점에서 도착점까지의 최단 경로를 효율적으로 찾을 수 있다. BFS는 큐를 사용하여 탐색하는 너비 우선 탐색 방식으로, 같은 거리의 모든 경로를 동시에 탐색하여 최단 경로를 구한다.