[프로그래머스] Level2 - 배달(Javascript)

프로그래머스

▶ 문제 요약

1. N개의 마을로 이루어진 마음이 있다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 한다. 

2. 도로를 지날 때 걸리는 시간은 도로별로 다르다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 한다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 한다. 

3. 음식을 주문을 받을 수 있는 마을의 개수를 return 해라.

 

▶ 정답 코드

function solution(N, road, K) {
    let answer = 0;
    let INF = Number.MAX_VALUE;
    let adj = Array.from({length : N + 1}, () => []);
    // 모든 마을까지의 최소시간을 무한대 설정
    let dist = Array.from({length : N + 1}, () => INF);
    
    // 인접리스트 생성
    road.forEach(([a, b, c]) => {
        adj[a].push({ to : b, time : c});
        adj[b].push({ to : a, time : c});
    });
    
    // 시작지점 
    let pq = [{ to : 1, time : 0}];
    // 시작지점 시간 표시
    dist[1] = 0;
    
    while (pq.length > 0) {
        // 우선수위 큐를 사용해서 가장 가까운 거리부터 탐색
        pq.sort((a, b) => a.time - b.time);
        // 순회를 위해서 현재 위치와 시간 빼기
        let {to, time} = pq.shift();
        
        // 현재 경로와 인접한 노드를 돌면서
        adj[to].forEach((next) => {
            // 다음 지점까지 현재 알려진 최단거리가 현재 지점 거쳐서 다음 지점까지 가는 거리 보다 길면
            if (dist[next.to] > dist[to] + next.time) {
                // 최단 거리를 갱신하고 
                dist[next.to] = dist[to] + next.time;
                // 인접한 노드와, 그 노드의 시간을 넣어준다. 
                pq.push({to : next.to, time : dist[next.to]});
            }
        });
        
        
    }
    
    for (let i = 1; i <= N; i++) {
        // 마을의 거리가 K 이하의 시간에 배달이 가능하면 answer++;
        if (dist[i] <= K) answer++;
    }
    return answer;
    
}

▶ 풀이 과정

1. 이 풀이는 각 마을까지 배달하는데 걸리는 최소 시간을 구하는 문제이므로,  다익스트라 알고리즘 문제이다. 먼저 인접리스트를 만들어줘야한다. 노드는 1번부터 시작하니까 N+1을 사용해서 빈 배열을 만들어준다. 그리고 모든 마을까지의 최소시간을 무한대로 설정한다. 

이 과정에서 수의 무한대를 나타내는 Number.MAX_VALUE를 사용했다. 

 

2. 주어진 입력값을 forEach() 구문을 사용해서 인접 리스트를 만들어준다. 여기서 객체에 인접 노드와 거리를 같이 담아줬다. 

 

3. 문제에서 주어진 것은 1번 마을에 있는 음식점에서 출발하는 것이 기본 조건이다. 따라서 시작 지점은 1번 노드이다. 그래서 배열 안에 다시 객체로 시작지점과 시작지점의 거리는 0으로 출발한다. 시작지점 시간을 0으로 설정한다. 

 

4. while문을 사용해서 큐가 있을 때까지 돌아준다. 그리고 핵심 파트 우선순위 큐를 사용했다. 우선순위 큐를 사용하면 가장 가까운 거리부터 탐색하니까 효율적이며 실제로 쓰지 않을 경우 시간 차이가 꽤 난다. 시간 순으로 정렬했다. 

 

5. 탐색을 위해 현재 위치와 시간을 큐에서 빼준다.

 

6. 아까 만들어 놓은 인접 리스트를 forEach() 메서드를 활용해서 해당 노드의 인접 노드를 돌면서 다음 지점까지 현재 알려진 최단거리가 현재 지점에서 다음 지점까지 가는 거리 보다 길면 최단경로를 갱신해준다. 쉽게 말해서 현재 최단거리라고 알려진 부분이 새로 이동하는 거리보다 크면 최단거리가 아니니까 바꿔주는 방식이다. 

 

7. 다음 돌아야 곳은 인접 노드이다. 따라서 큐에 인접 노드와 현재 알려진 인접 노드의 최단거리를 넣어준다. 

 

8. 이제 모든 마을까지의 거리를 돌면서 K시간 이하이면 answer에 1씩 더해주고 결과값을 출력한다.