미로 [2178]

문제

https://www.acmicpc.net/problem/2178

N×M크기의 배열로 표현되는 미로가 있다.

1	0	1	1	1	1
1	0	1	0	1	0
1	0	1	0	1	1
1	1	1	0	1	1

미로에서 1은 이동할 수 있는 칸을 나타내고, 0은 이동할 수 없는 칸을 나타낸다. 이러한 미로가 주어졌을 때, (1, 1)에서 출발하여 (N, M)의 위치로 이동할 때 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성하시오. 한 칸에서 다른 칸으로 이동할 때, 서로 인접한 칸으로만 이동할 수 있다.

위의 예에서는 15칸을 지나야 (N, M)의 위치로 이동할 수 있다. 칸을 셀 때에는 시작 위치와 도착 위치도 포함한다.

입력

첫째 줄에 두 정수 N, M(2 ≤ N, M ≤ 100)이 주어진다. 다음 N개의 줄에는 M개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

나의 접근

미로를 다 지나야 하는 최소의 칸 수를 구하는 프로그램을 작성해야 하므로 항상 같은 깊이의 노드들을 먼저 탐색하는 BFS를 사용했다.

코드

const readline = require('readline');

// readline 인터페이스 생성
const rl = readline.createInterface({
    input: process.stdin,
    output: process.stdout
});

// 질문을 받아 처리할 배열
let input = [];
rl.on('line', function (line) {
    input.push(line);
}).on('close', function () {
    let [Y, X] = input[0].split(" ").map(Number); // Y: 행, X: 열
    let maze = Array.from({ length: Y }, () => Array(X).fill(0)); // 미로 초기화
    let visited = Array.from({ length: Y }, () => Array(X).fill(false)); // 방문 여부 초기화
    let distance = Array.from({ length: Y }, () => Array(X).fill(0)); // 거리를 저장하는 배열

    // 미로 정보 입력 처리
    for (let i = 0; i < Y; i++) {
        maze[i] = input[i + 1].split("").map(Number); // 미로 배열에 입력된 값들을 숫자로 변환
    }

    let direction = [[1, 0], [-1, 0], [0, 1], [0, -1]]; // 상, 하, 좌, 우 방향
    let queue = [[0, 0]]; // BFS를 위한 큐
    visited[0][0] = true; // 시작점 방문 처리
    distance[0][0] = 1; // 시작점 거리는 1

    // BFS 시작
    while (queue.length > 0) {
        let [y, x] = queue.shift(); // 큐에서 현재 좌표를 꺼냄

        // 네 방향 탐색
        direction.forEach(([dy, dx]) => {
            let newY = y + dy;
            let newX = x + dx;

            // 유효한 범위이고, 아직 방문하지 않았으며, 이동할 수 있는 칸인 경우
            if (newX >= 0 && newY >= 0 && newX < X && newY < Y && !visited[newY][newX] && maze[newY][newX] === 1) {
                visited[newY][newX] = true; // 방문 처리
                queue.push([newY, newX]); // 큐에 좌표 추가
                distance[newY][newX] = distance[y][x] + 1; // 이동한 거리 갱신
            }
        });
    }

    // 도착 지점의 최단 거리 출력
    console.log(distance[Y - 1][X - 1]);
    rl.close();
});

복잡도 분석

• 시간 복잡도: 미로의 모든 노드를 탐색하고, 각 노드에서 4방향을 확인하는 과정을 포함하므로 O(Y * X)
• 공간 복잡도: 미로 배열, 방문 배열, 거리 배열, BFS 큐 모두 Y * X 크기의 메모리를 사용하므로 O(Y * X)

배운 점

• 미로문제같은 경우에는 BFS방식을 사용해야 최단 경로를 계산할 수 있다.