[알고리즘] 부대복귀 / JavaScript / 프로그래머스 Lv.3

📖 문제

문제 풀러 가기

문제 설명

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 1로 동일합니다. 임무를 수행한 각 부대원은 지도 정보를 이용하여 최단시간에 부대로 복귀하고자 합니다. 다만 적군의 방해로 인해, 임무의 시작 때와 다르게 되돌아오는 경로가 없어져 복귀가 불가능한 부대원도 있을 수 있습니다.

강철부대가 위치한 지역을 포함한 총지역의 수 n, 두 지역을 왕복할 수 있는 길 정보를 담은 2차원 정수 배열 roads, 각 부대원이 위치한 서로 다른 지역들을 나타내는 정수 배열 sources, 강철부대의 지역 destination이 주어졌을 때, 주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 담은 배열을 return하는 solution 함수를 완성해주세요. 복귀가 불가능한 경우 해당 부대원의 최단시간은 -1입니다.

제한사항

• 3 ≤ n ≤ 100,000
  • 각 지역은 정수 1부터 n까지의 번호로 구분됩니다.
• 2 ≤ roads의 길이 ≤ 500,000
  • roads의 원소의 길이 = 2
  • roads의 원소는 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미합니다.(1 ≤ a, b ≤ n, a ≠ b)
  • 동일한 정보가 중복해서 주어지지 않습니다.
    • 동일한 [a, b]가 중복해서 주어지지 않습니다.
    • [a, b]가 있다면 [b, a]는 주어지지 않습니다.
• 1 ≤ sources의 길이 ≤ 500
  • 1 ≤ sources[i] ≤ n
• 1 ≤ destination ≤ n

입출력 예

n	roads	sources	destination	result
3	[[1, 2], [2, 3]]	[2, 3]	1	[1, 2]
5	[[1, 2], [1, 4], [2, 4], [2, 5], [4, 5]]	[1, 3, 5]	5	[2, -1, 0]

입출력 예 설명

입출력 예 #1

• 지역 2는 지역 1과 길로 연결되어 있기 때문에, 지역 2에서 지역 1의 최단거리는 1입니다.
• 지역 3에서 지역 1로 이동할 수 있는 최단경로는 지역 3 → 지역 2 → 지역 1 순으로 이동하는 것이기 때문에, 지역 3에서 지역 1의 최단거리는 2입니다.
• 따라서 [1, 2]를 return합니다.

입출력 예 #2

• 지역 1에서 지역 5의 최단경로는 지역 1 → 지역 2 → 지역 5 또는 지역 1 → 지역 4 → 지역 5 순으로 이동하는 것이기 때문에, 최단거리는 2입니다.
• 지역 3에서 지역 5로 가는 경로가 없기 때문에, 지역 3에서 지역 5로 가는 최단거리는 -1입니다.
• 지역 5에서 지역 5는 이동할 필요가 없기 때문에, 최단거리는 0입니다.
• 따라서 [2, -1, 0]을 return합니다.

---

🧮 풀이 1

각 지역에서 강철부대가 위치한 지역 destination까지 최단시간에 이동해야 하며, 두 지역 간의 길을 통과하는 데 걸리는 시간이 모두 1로 동일하므로 BFS 알고리즘을 이용하였습니다.

다음과 같은 방법으로 문제에 접근했습니다.

1️⃣ 각 지역의 연결 정보를 담은 인접 리스트 graph 배열 생성

roads 배열의 원소가 [a, b] 형태로 두 지역 a, b가 서로 왕복할 수 있음을 의미하므로 a 지역에서 b 지역으로, b 지역에서 a 지역으로 이동할 수 있음을 graph에 기록합니다.

let graph = Array.from({length: n + 1}, () => []);
for (let [a, b] of roads) {
    graph[a].push(b);
    graph[b].push(a);
}

2️⃣ sources 배열 순회

주어진 sources의 원소 순서대로 강철부대로 복귀할 수 있는 최단시간을 계산해야 하므로 sources 배열을 순회하며 최단경로를 계산하는 BFS 함수를 실행할 것입니다.

for (let source of sources) {
  	...
}

3️⃣ 강철부대가 위치한 destination까지 최단경로를 계산하는 BFS 함수 설계

sources의 원소 source에서 출발하여 destination으로 가는 최단경로를 계산하는 BFS 함수를 작성합니다. destination에 도착하면 최단경로를, 도착할 수 없다면 -1을 반환하도록 합니다.

function BFS(start) {
    let visited = Array(n + 1).fill(false);
    visited[start] = true;
    let queue = [[start, 0]];

    while (queue.length) {
      let [cur, dist] = queue.shift();

      if (cur === destination) return dist;

      for (let next of graph[cur]) {
        if (visited[next]) continue;

        visited[next] = true;
        queue.push([next, dist + 1]);
      }
    }

    return -1;
}

4️⃣ 반복문 내부에서 BFS 실행

sources를 순회하는 반복문 내부에서 최단경로를 계산하는 BFS 함수를 실행하고 결과값을 answer 배열에 저장합니다.

for (let source of sources) {
  	answer.push(BFS(source));
}

🌕 전체 코드

전체 코드는 다음과 같습니다.

function solution(n, roads, sources, destination) {
    let answer = [];
    
    let graph = Array.from({length: n + 1}, () => []);
    for (let [a, b] of roads) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    function BFS(start) {
        let visited = Array(n + 1).fill(false);
        visited[start] = true;
        let queue = [[start, 0]];
        
        while (queue.length) {
            let [cur, dist] = queue.shift();
            
            if (cur === destination) return dist;
            
            for (let next of graph[cur]) {
                if (visited[next]) continue;
                
                visited[next] = true;
                queue.push([next, dist + 1]);
            }
        }
        
        return -1;
    }
    
    for (let source of sources) {
        answer.push(BFS(source));
    }
    
    return answer;
}

🧪 실행결과

위 코드를 실행하면 주어진 입출력 예에 대해 올바른 결과값이 나타날 것입니다. 하지만 코드를 제출 후 채점하면, 아래와 같이 시간 초과가 발생하는 것을 확인할 수 있습니다.

무엇이 문제일까요?

⚠️ 문제 원인 분석

문제가 발생한 원인을 알아보기 위해 제한사항과 작성한 코드의 시간 복잡도를 반드시 확인해야 합니다. 먼저 문제의 제한사항을 다시 살펴봅시다.

• n: 100,000 이하
• roads의 길이: 500,000 이하
• sources의 길이: 500 이하

다음으로, 작성한 코드의 시간 복잡도를 살펴봅시다.

1️⃣ 첫 번째 과정에서 roads 배열을 순회하므로 시간 복잡도는 roads의 길이를 따를 것입니다. roads의 길이를 e라고 하면 시간 복잡도는 $O(e)=O(500,000)$입니다.

3️⃣ 세 번째 과정에서 BFS를 수행합니다. 인접 리스트 형태의 graph를 순회하는 BFS이므로 이 과정에서는 visited 배열을 생성하는데 $O(n)$, BFS 탐색에 $O(n+e)$가 소요되어 최종적으로 시간 복잡도는 $O(n+e)=O(600,000)$입니다.

4️⃣ 네 번째 과정에서 BFS를 sources의 길이만큼 반복합니다. sources의 길이를 k라고 하면, 최종적으로 이 풀이의 시간 복잡도는 $O(e)+O(k * (n+m))=O(300,500,000)$으로 최악의 경우 약 3억 번의 연산이 필요하게 됩니다.

이로 인해 시간 초과가 발생했던 것입니다.

---

🧮 풀이 2

그렇다면 풀이 1을 어떻게 개선할 수 있을까요?

이 문제의 핵심은 sources의 길이는 최대 500이지만 destination이 하나라는 점입니다. 즉, sources를 순회하며 매번 BFS를 수행하는 것이 아니라, destination에서 출발하여 각 지역까지 가는 최단경로를 배열에 저장하는 방법을 이용한다면, 1번의 BFS 수행으로 문제를 해결할 수 있습니다.

graph 배열 생성은 풀이 1과 동일합니다.

1️⃣ destination에서 각 지역으로 가는 최단경로를 저장할 distance 배열 생성

destination에서 출발하여 각 지역까지 가는 최단경로를 저장할 distance 배열을 생성하고, 배열의 원소를 -1로 초기화합니다. 해당 지역에 도달할 수 없는 경우 -1을 반환해야 하기 때문입니다. 또한, 역으로 수행하는 BFS의 출발점인 destination까지의 거리를 0으로 설정합니다.

let distance = Array(n + 1).fill(-1);
distance[destination] = 0;

2️⃣ destination부터 BFS 수행

풀이 1과는 반대로 destination에서 출발하여 각 지역까지 가는 최단경로를 탐색하고, 도달할 수 있다면 이전 지역까지 최단경로 + 1 값을 distance[지역] 값으로 저장합니다.

let queue = [[destination]];        
while (queue.length) {
    let cur = queue.shift();

    for (let next of graph[cur]) {
      if (distance[next] !== -1) continue;

      distance[next] = distance[cur] + 1;
      queue.push([next]);
    }
}

3️⃣ sources 배열을 순회하며 distance 값을 반환

마지막으로 sources 배열의 각 원소까지 가는 경로를 순서대로 distance 배열에서 탐색하여 값을 반환합니다.

return sources.map((source) => distance[source]);

🌕 전체 코드

전체 코드는 다음과 같습니다.

function solution(n, roads, sources, destination) {    
    let graph = Array.from({length: n + 1}, () => []);
    for (let [a, b] of roads) {
        graph[a].push(b);
        graph[b].push(a);
    }
    
    let distance = Array(n + 1).fill(-1);
    distance[destination] = 0;
    
    let queue = [[destination]];        
    while (queue.length) {
        let cur = queue.shift();

        for (let next of graph[cur]) {
            if (distance[next] !== -1) continue;

            distance[next] = distance[cur] + 1;
            queue.push([next]);
        }
    }
    
    return sources.map((source) => distance[source]);
}

🧪 실행결과

새로 작성한 풀이를 제출 후 채점하면, 이번에는 모든 테스트 케이스에 대해 문제 없이 통과하는 것을 확인할 수 있습니다.

✅ 성공 원인 분석

그렇다면 이번에는 어떤 부분이 개선되어 정답이 될 수 있었을까요? 다시 한 번 문제의 제한사항을 다시 살펴봅시다.

• n: 100,000 이하
• roads의 길이: 500,000 이하
• sources의 길이: 500 이하

다음으로, 작성한 코드의 시간 복잡도를 살펴봅시다.

풀이 1과 마찬가지로 graph 배열을 생성하는 과정에서 roads 배열을 순회하므로 시간 복잡도는 roads의 길이를 따를 것입니다. roads의 길이를 e라고 하면 시간 복잡도는 $O(e)=O(500,000)$입니다.

2️⃣ 두 번째 과정에서 BFS를 수행합니다. 인접 리스트 형태의 graph를 순회하는 BFS이므로 탐색하는 데 소요되는 시간 복잡도는 $O(n+e)=O(600,000)$입니다.

3️⃣ 세 번째 과정에서 sources의 원소를 순회하며 distance[source]의 값을 탐색합니다. sources의 길이를 k라고 하면, 최종적으로 이 풀이의 시간 복잡도는 $O(n+e+k)=O(600,500)$으로 최악의 경우 약 60만 번의 연산을 필요로 합니다.

풀이 1에서 최악의 경우 3억 번의 연산이 필요했던 것을 생각하면 연산 횟수를 약 99.8% 개선하여 시간 초과 문제를 완벽히 해결할 수 있습니다.