프로그래머스 게임 맵 최단거리

링크 : https://school.programmers.co.kr/learn/courses/30/lessons/1844

문제 풀이

dfs로 풀이한 내용 (더보기 -> 효율성 테스트 실패)

dfs를 이용하여 최단거리를 구할 경우 정답은 되지만 효율성 측면에서 통과를 하지 못한다.

그 이유는 모든 경로를 다 확인하므로 최단거리를 빠르게 구하는 알고리즘 자체는 bfs가 더 효율적

function solution(maps) {
    var answer = Infinity;
    
    let dx = [0, 0, 1, -1];
    let dy = [1, -1, 0, 0];
    let n = maps.length;
    let m = maps[0].length;
    let visited = Array.from({length: n}, () => Array.from({length: m}, () => 1));
    
    function dfs(x, y, cnt) {
        if (answer <= cnt) return;
        if (x === m - 1 && y === n - 1) {
            answer = Math.min(answer, cnt);
            return;
        }
        
        for (let i = 0; i < 4; i++) {
            let newX = x + dx[i];
            let newY = y + dy[i];
            if (newX >= 0 && newX < m && newY >= 0 && newY < n && visited[newY][newX] && maps[newY][newX]) {
                visited[newY][newX] = 0;
                dfs(newX, newY, cnt + 1);
                visited[newY][newX] = 1;
            }
        }
    }
    
    visited[0][0] = 0;
    dfs(0, 0, 1);
    
    return answer === Infinity ? -1 : answer;
}

dfs를 이용하여 문제를 풀 경우 모든 경로를 검사하므로 최단거리를 찾는데 효율성 측면에서 통과를 하지 못함

bfs는 가장 먼저 도착한 경로가 최단 거리를 나타내므로 모든 경로를 검사할 필요가 없어짐

-> 처음 도착한 것이 최단거리이므로 최악의 경우 시간복잡도가 O(n * m)임

(dfs로 접근할 경우 최악의 경우 O(4^(n * m)) -> 4방향의 n*m만큼 지수적으로 증가함)

function solution(maps) {
    let dx = [0, 0, 1, -1];
    let dy = [1, -1, 0, 0];
    
    let n = maps.length;
    let m = maps[0].length;
    let visited = Array.from({length: n}, () => Array.from({length: m}, () => false));
    visited[0][0] = true;
    maps[0][0] = 0;
    
    let q = [[0, 0, 1]];
    
    while (q.length > 0) {
        let [x, y, dist] = q.shift();
        
        if (x === m - 1 && y === n - 1) {
            return dist;
        }
        
        for (let i = 0; i < 4; i++) {
            const newX = x + dx[i];
            const newY = y + dy[i];
            
            if (newX >= 0 && newX < m &&
               newY >= 0 && newY < n &&
               maps[newY][newX] &&
               !visited[newY][newX]) {
                visited[newY][newX] = true;
                q.push([newX, newY, dist + 1]);
            }
        }
    }
    
    return -1;
}

---

결론

최단거리 찾는 문제는 dfs보단 bfs가 더 좋을 수 있다는 것을 생각하기 -> 모든 경로를 파악하지 않으니까