[DFS 문제] 경로 탐색(미로 탐색, 최단 경로)

난이도 2 - 경로 탐색 (예상 소요 시간: 10~15분)

🔹 문제: 미로 탐색

N x M
크기의 미로가 주어진다. (1,1)에서 시작해 (N,M)으로 가는 최단 경로를 DFS로 탐색하여 출력하시오.
벽(0)과 길(1)로 이루어져 있으며, 상하좌우로 이동 가능하다.

 

입력 예시:

4 4  
1 1 0 1  
1 1 1 1  
0 1 0 1  
1 1 1 1

 

출력 예시:

최단 거리: 7 // 0,0 -> 4,4

 

 

console.log(solution(5, 5, [
    [1, 1, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 1, 0],
    [1, 1, 1, 1, 1],
    [0, 0, 0, 0, 1]
])); 
// 예상 결과: 9

console.log(solution(4, 4, [
    [1, 0, 0, 1],
    [1, 0, 1, 1],
    [0, 0, 1, 0],
    [1, 1, 0, 1]
]));
// 예상 결과: -1

 

 

 

🔹 코드

function solution(x, y, arr) {
    let minRoot = Number.MAX_SAFE_INTEGER;
    let dx = [1, 0, -1, 0];
    let dy = [0, 1, 0, -1];

    function dfs(x, y, count) {
        // 목적지 도착 시 최단거리 갱신
        if (x === arr[0].length - 1 && y === arr.length - 1) {
            minRoot = Math.min(count, minRoot);
            return;
        }

        // 방문 체크 (진입 시 0으로 변경)
        arr[y][x] = 0;

        for (let i = 0; i < 4; i++) {
            let nx = x + dx[i];
            let ny = y + dy[i];

            // 범위 체크 & 방문 가능 여부 확인
            if (nx >= 0 && nx < arr[0].length && ny >= 0 && ny < arr.length && arr[ny][nx] === 1) {
                dfs(nx, ny, count + 1);
            }
        }

        // 백트래킹 (다른 경로 탐색을 위해 원상 복구)
        arr[y][x] = 1;
    }

    // DFS 시작 (0,0에서 count=1부터)
    dfs(0, 0, 1);

    return minRoot !== Number.MAX_SAFE_INTEGER ? minRoot : -1;
}

 

최단경로 문제는 보통 BFS(너비 우선 탐색)로 해결하는 것이 더 적합! 😅

왜 BFS가 더 적합한지?

• DFS는 깊이 우선 탐색이기 때문에, 한 경로를 끝까지 탐색한 뒤 다른 경로를 탐색한다. 이 방식은 경로의 길이를 고려하지 않고 탐색을 진행한다.
• BFS는 모든 인접 노드를 먼저 탐색한 뒤, 그다음 레벨의 노드를 탐색하는 방식이므로 최단 경로를 자연스럽게 찾을 수 있다.

BFS를 사용하면, `한 번에 한 칸씩 확장해 나가기 때문에 최단 거리를 보장하면서 탐색할 수 있다!

DFS는 경로 탐색에 적합하지만, 최단 거리 문제에서는 BFS가 훨씬 효율적이고 자연스러움