배달(Lv.2)

 

---

 

문제 설명

 

 

 

입출력 예시

 

 

요약

1번 마을에서 출발해서 K 이하의 시간으로 배달 가능한 모든 마을의 개수 구하기

 

---

 

풀이

 

접근 방식

1. 방문 가능한 모든 경로 찾기

  → 간선의 가중치(소요 시간)와 도착 마을의 번호를 담는 객체 클래스(Node) 생성

  → graph라는 배열에 특정 마을의 인접한 마을의 Node리스트를 저장

  → 마을을 잇는 간선은 방향이 없기 때문에 반대의 경우도 함께 저장

 

2. 최소 비용으로 마을 방문하기

  → 다익스트라(dijkstra) 알고리즘을 통해 최소비용으로 방문하는 경우를 구한다.

 

3. 배달 가능한 마을의 개수 구하기

  → K 이하의 비용이 드는 마을의 개수를 카운팅해서 리턴

 

---

 

코드 리뷰

 

import java.util.*;

// 도착 지점의 번호와 간선의 가중치를 담는 Node 객체 클래스
class Node {
    int index;	// 도착 지점 번호
    int cost;	// 간선의 가중치
    public Node(int index, int cost) {
        this.index = index;
        this.cost = cost;
    }
}

class Solution {
    int N, K;
    ArrayList<Node>[] graph;	// 모든 경로를 담을 graph 배열
    
    public int dijkstra(int start) {	// 다익스트라 알고리즘을 통해 최소 비용으로 방문
        boolean[] visited = new boolean[N+1];	// 재방문 방지를 위한 visited 배열
        int[] dist = new int[N+1];	// 방문시 필요한 비용을 담을 dist 배열
        Arrays.fill(dist, Integer.MAX_VALUE);	// 최초 비용은 MAX_VALUE로 설정
        
        // 우선순위 큐를 활용해 간선의 가중치가 적은 순으로 디큐
        // 우선순위를 비교하기 위해 Node 객체에 Comparable을 implements하고 compareTo() 메소드를 오버라이딩 해도 되고,
        // 아래처럼 람다식으로 Comparator의 compare() 메소드의 리턴값을 표기해도 됨
        PriorityQueue<Node> pq = new PriorityQueue<>((a, b) -> a.cost - b.cost);	
        pq.add(new Node(start, 0));	// 처음 큐에 담을 객체는 시작 마을의 번호(= start)와 시작 마을의 가중치(=0)
        dist[start] = 0;	// 시작 마을까지의 거리는 0으로 초기화
        
        while(!pq.isEmpty()) {
            int now = pq.poll().index;	// 우선순위 큐이기 때문에 가중치가 낮은 순으로 디큐됨
            if(visited[now]) continue;	// 방문한 마을이라면 건너 뛰고
            visited[now] = true;	// 방문했음을 표시
            // graph에는 인접 노드의 정보가 담겨 있음(now가 1이라면 graph[1]에는 1번 마을에 대한 인접 마을의 번호와 각 간선의 가중치를 담은 Node 리스트가 있음)
            for(Node adj : graph[now]) {	// Node adj에는 인접 마을의 정보를 담은 Node 객체가 담김
                dist[adj.index] = Math.min(dist[adj.index], dist[now] + adj.cost);	// 인접 마을까지의 거리(dist)를 최소 비용으로 설정
                pq.add(new Node(adj.index, dist[adj.index]));	// 최소 비용으로 새롭게 갱신된 인접 마을에 대한 정보를 담은 Node 객체를 우선순위 큐에 추가
            }
        }
        return (int)Arrays.stream(dist).filter(k -> k <= K).count();	// K이하의 비용으로 방문할 수 있는 마을의 개수 카운팅
    }
    
    public int solution(int N, int[][] road, int K) {
        this.N = N;
        this.K = K;
        graph = new ArrayList[N+1];	// graph 배열 크기를 전체 마을의 개수 + 1 로 설정
        for(int i = 0; i < graph.length; i++) {
            graph[i] = new ArrayList<>();	// graph의 각 인덱스를 new ArrayList로 초기화
        }
        for(int[] arr : road) {
            int u = arr[0];	// 출발지
            int v = arr[1];	// 도착지
            int cost = arr[2];	// 간선의 가중치
            graph[u].add(new Node(v, cost));	// u마을의 인접 마을로 v 마을 번호와 간선의 가중치를 담는다.
            graph[v].add(new Node(u, cost));	// v마을의 인접 마을로 u 마을 번호와 간선의 가중치를 담는다.
        }
        return dijkstra(1);	// 다익스트라 알고리즘 실행
    }
}

 

---

 

추가 자료

 

다익스트라 알고리즘 실행 순서

이미지 출처: 위키피디아

 

 

출력 로그와 함께 보기

시작 노드 : 1번
<1번 노드>를 방문합니다.
인접 노드 = 2, 시작 노드(1번)부터 해당 노드까지의 거리 = 2147483647
1번 노드부터 인접 노드까지의 거리를 갱신합니다. 갱신 후 거리 = 1
인접 노드 = 4, 시작 노드(1번)부터 해당 노드까지의 거리 = 2147483647
1번 노드부터 인접 노드까지의 거리를 갱신합니다. 갱신 후 거리 = 2

<2번 노드>를 방문합니다.
인접 노드 = 1, 시작 노드(1번)부터 해당 노드까지의 거리 = 0
현재 시작 노드(1번)부터 1번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 3, 시작 노드(1번)부터 해당 노드까지의 거리 = 2147483647
1번 노드부터 인접 노드까지의 거리를 갱신합니다. 갱신 후 거리 = 4
인접 노드 = 5, 시작 노드(1번)부터 해당 노드까지의 거리 = 2147483647
1번 노드부터 인접 노드까지의 거리를 갱신합니다. 갱신 후 거리 = 3

<4번 노드>를 방문합니다.
인접 노드 = 1, 시작 노드(1번)부터 해당 노드까지의 거리 = 0
현재 시작 노드(1번)부터 1번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 5, 시작 노드(1번)부터 해당 노드까지의 거리 = 3
현재 시작 노드(1번)부터 5번 노드까지는 최단 거리이므로 갱신하지 않습니다.

<5번 노드>를 방문합니다.
인접 노드 = 2, 시작 노드(1번)부터 해당 노드까지의 거리 = 1
현재 시작 노드(1번)부터 2번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 3, 시작 노드(1번)부터 해당 노드까지의 거리 = 4
현재 시작 노드(1번)부터 3번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 4, 시작 노드(1번)부터 해당 노드까지의 거리 = 2
현재 시작 노드(1번)부터 4번 노드까지는 최단 거리이므로 갱신하지 않습니다.

<3번 노드>를 방문합니다.
인접 노드 = 2, 시작 노드(1번)부터 해당 노드까지의 거리 = 1
현재 시작 노드(1번)부터 2번 노드까지는 최단 거리이므로 갱신하지 않습니다.
인접 노드 = 5, 시작 노드(1번)부터 해당 노드까지의 거리 = 3
현재 시작 노드(1번)부터 5번 노드까지는 최단 거리이므로 갱신하지 않습니다.

dist[] 배열을 index = 1부터 출력합니다.
dist[] = {0, 1, 4, 2, 3}