[프로그래머스] 부대복귀 - JavaScript

문제 출처

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

프로그래머스

문제 설명

강철부대의 각 부대원이 여러 지역에 뿔뿔이 흩어져 특수 임무를 수행 중입니다. 지도에서 강철부대가 위치한 지역을 포함한 각 지역은 유일한 번호로 구분되며, 두 지역 간의 길을 통과하는 데 걸리는 시간은 모두 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

---

입출력 예

입출력 예 설명

입출력 예 #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합니다.

풀이 방법

• 인접리스트를 활용하여 목적지를 시작으로 source 내의 요소에 접근 가능한지 판단하였다.
• distance 배열을 -1(닿지 못하는것을 가정으로)로 초기화하고, bfs를 이용하여 목적지부터 source요소 내의 거리를 계산하였다.

풀이 코드

function solution(n, roads, sources, destination) {
    let answer = [];
    let adjList = Array.from({ length: n + 1 }, () => []);
    
    roads.forEach((road) => {
        adjList[road[0]].push(road[1]);
        adjList[road[1]].push(road[0]);
    });
    
    let distance = new Array(n + 1).fill(-1);
    //자기 위치는 0이다.
    distance[destination] = 0;
    let queue = [[destination, 0]];
    while(queue.length > 0){
        let [cur, dist] = queue.shift();
        //현재 요소와 연결된 곳 탐방
        for(let next of adjList[cur]){
            if(distance[next] === -1){
                distance[next] = dist + 1;
                queue.push([next, dist + 1]);
            }
        }
    }
    
    sources.forEach((source, idx) => {
        answer[idx] = distance[source];
    });
   
    return answer;
}

결과

회고

• 왜이리 시간이 오래걸리는것인가

바뀐 풀이

• 검색을 해보니까 shift연산에 시간이 매우 많이 소요된다는 점을 알았다. 그래서 shift를 없애고, head와 tail을 이용하여 shift없이 그냥 배열을 밀면서 계산해보기로 하였다.

바뀐 풀이 코드

function solution(n, roads, sources, destination) {
    let answer = [];
    let adjList = Array.from({ length: n + 1 }, () => []);
    
    roads.forEach((road) => {
        adjList[road[0]].push(road[1]);
        adjList[road[1]].push(road[0]);
    });
    
    let distance = new Array(n + 1).fill(-1);
    //자기 위치는 0이다.
    distance[destination] = 0;
    let queue = new Array(n);
    let head = 0, tail = 0;
    
    queue[tail++] = destination;
    
    while(head < tail){
        let cur = queue[head++];
        
        for(let next of adjList[cur]){
            if(distance[next] === -1){
                distance[next] = distance[cur] + 1;
                queue[tail++] = next;
            }
        }
    }
    sources.forEach((source, idx) => {
        answer[idx] = distance[source];
    });
   
    return answer;
}

바뀐 코드 결과