프로그래머스 [Lv. 3] 부대 복귀 {언어 : JavaScript}

문제 링크

https://school.programmers.co.kr/learn/courses/30/lessons/132266?language=javascript

프로그래머스

정답 코드

function solution(n, roads, sources, destination) {
    const answer = [];
    
    // 노드 저장
    const adjL = Array(n+1).fill().map(() => []);
    for (const [start, to] of roads) {
        adjL[start].push(to);
        adjL[to].push(start);
    };
    
    // destination에서 출발하는 너비 우선 탐색
    let visited = Array(n+1).fill().map(() => -1);
    const q = [destination];
    visited[destination] = 0;
    while (q.length) {
        const cd = q.shift();
        for (const nd of adjL[cd]) {
            if (visited[nd] == -1) {
                visited[nd] = visited[cd] + 1;
                q.push(nd);
            };
        };
    };
    
    for (const source of sources) {
        answer.push(visited[source]);
    };
    
    return answer;
}

풀이 방법

1. 각 부대원들이 각자 출발해서 도착지점으로 이동하게 만드는 것이 아니다.
2. 도착지점에서 출발해서 visited에 걸린 시간을 기록한다.
   
   1. 걸린 시간을 기록하는 알고리즘은 dp
   2. 각 지점까지 이동하는 알고리즘은 bfs
3. sources의 각 부대원의 해당 위치의 걸린 시간을 visited[source]
4. 걸린 시간들을 answer에 넣고 반환하면 끝!

느낀점

• 문제를 잘 읽고 천천히 접근한 결과 쉽게 풀 수 있었다.