프로그래머스 - 부대복귀 (JavaScript)

문제

https://school.programmers.co.kr/learn/courses/30/lessons/132266

프로그래머스

 

생각해보기

시도해본 방법

1. shift 연산 → queue 구현

2. 방문 체크 자료구조 : 배열 → Map 객체

3. 인접 리스트 자료구조 : 2차원 배열 → Map 객체

 

 

index를 알고 있으면 배열 또한 탐색을 O(1)로 수행할 수 있으므로 차이가 없었다. 그러나 2, 3의 경우 길이 없는 지역에 대해 (key, value)를 할당하지 않으므로 특정 조건 하에(길이 없는 지역이 많을 경우) 메모리 효율성은 좋아질 수 있을 것이다.

 

 

정확히 어떤 연산이 오래 걸리는지 파악하지 못했기 때문에 위와 같이 여러 방법들을 시도했던 것 같다. 그래프(인접 행렬, 인접 리스트)에 따른 BFS/DFS의 시간 복잡도를 구체적으로 계산하지 않았던 것이 문제였다.

 

 

노드의 개수를 V라고 하자. 인접 행렬의 경우 임의의 노드에서 다른 모든 노드에 대한 간선 존재 여부를 확인하는 과정이 있다. 그리고 해당 연산이 모든 노드들에 대해 수행된다. 따라서 시간 복잡도는 O(V^2)이다.

 

 

인접 리스트의 경우 임의의 노드에 대해 간선이 존재하는 노드만 탐색한다. 그리고 해당 연산이 모든 노드들에 대해 수행된다. 따라서 시간 복잡도는 O(V+E)이다.

 

 

sources의 최대 길이는 500이다. 노드는 최대 10만개, 간선은 최대 50만개가 존재할 수 있다. 그리고 각 source마다 visited 초기화 연산 또한 수행되어야 한다. 따라서 극단적인 경우 약 3억번 이상의 연산(500 × (10만 + 50만 + 10만))을 수행해야 한다.

 

 

그러나 도착점을 기준으로 모든 노드들에 대해 탐색을 수행하면 출발 지점들에 대해 순회를 하지 않아도 된다.

 

풀이

function solution(n, roads, sources, destination) {
    
    var answer = [];
    let graph = Array.from({ length: n + 1 }, () => []);
    let visited = Array.from({ length: n + 1 }, () => -1);
    
    for (const road of roads) {
        graph[road[0]].push(road[1]);
        graph[road[1]].push(road[0]);
    }
    
    const bfs = (end) => {        
        let queue = [end]
        visited[end] = 0;
        
        while (queue.length) {
            let now = queue.shift();
            
            for (const element of graph[now]) {
                if (visited[element] === -1) {
                    queue.push(element);
                    visited[element] = visited[now] + 1;
                }
            }
        }
    };
    
    bfs(destination);
    
    for (const source of sources) {
        answer.push(visited[source]);
    }
    
    return answer;
}