[JS] 백준 2178번 미로 탐색

 

출처

백준 온라인 저지

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

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개의 정수로 미로가 주어진다. 각각의 수들은 붙어서 입력으로 주어진다.

풀이

최단거리를 구하는 이 문제에서는 dfs 방식은 알맞지 않습니다.

dfs는 깊이 우선 탐색으로 결국 모든 경로를 탐색을 마친 후 종료되므로 이 문제에서는 시간 복잡도가 엄청납니다.

 

 

처음에는 visit란 배열에 방문한 경로를 저장하여 중복 방문을 막아보았지만 시간 초과란 결과가 나왔습니다.

그 후 생각을 바꿔 한번 지나간 경로 배열의 값을 이동한 거리로 바꿔 지나갈 수 없는 경로로 바꾸는 방식을 사용해보았습니다.

 

입력된 값들이 각 수가 붙어서 입력이 주어지므로 ( "00100" ) 이들을 모두 쪼개 배열로 만들어줍니다.

그리고 dir 란 변수에 4방향의 값을 담아두고 반복문을 이용하여 방향을 체크해줍니다. (if문 4번이란 방법도 존재합니다)

 

반복문을 돌려 경로가 방문할 수 있는 경로일 시 해당 경로 배열에는 현재 이동한 거리 값을 저장해줍니다.

모든 배열을 완전 탐색하여 나온 거리 값은 도착 위치(N, M)에도 저장됩니다.

 

코드

const input = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n');

const [yMax, xMax] = input.shift().split(" ");

const map = input.map(v => v.split("").map(x => +x));

const stack = [[0, 0, 1]];

const dir = [
    [0, 1],
    [0, -1],
    [1, 0],
    [-1, 0]
];

while (stack.length) {
    const [x, y, dis] = stack.shift();

    for (let i = 0; i < 4; i++) {
        const xPos = x + dir[i][0];
        const yPos = y + dir[i][1];
        
        if (0 <= xPos && yPos > -1 && xPos < xMax && yPos < yMax) {
            if (map[yPos][xPos] === 1) {
                map[yPos][xPos] = dis + 1;
                stack.push([xPos, yPos, dis+1]);
            }
        }
    }
}

console.log(map[yMax-1][xMax-1]);