Programmers | Level 2 | 배달

Programmers | Level 2 | 배달

Problems

• 📘 Src: Programmers
• 🗂️ Cat: Graph

󰧭 Description

N개의 마을로 이루어진 나라가 있습니다. 이 나라의 각 마을에는 1부터 N까지의 번호가 각각 하나씩 부여되어 있습니다. 각 마을은 양방향으로 통행할 수 있는 도로로 연결되어 있는데, 서로 다른 마을 간에 이동할 때는 이 도로를 지나야 합니다. 도로를 지날 때 걸리는 시간은 도로별로 다릅니다. 현재 1번 마을에 있는 음식점에서 각 마을로 음식 배달을 하려고 합니다. 각 마을로부터 음식 주문을 받으려고 하는데, N개의 마을 중에서 K 시간 이하로 배달이 가능한 마을에서만 주문을 받으려고 합니다. 다음은 N = 5, K = 3인 경우의 예시입니다.

위 그림에서 1번 마을에 있는 음식점은 [1, 2, 4, 5] 번 마을까지는 3 이하의 시간에 배달할 수 있습니다. 그러나 3번 마을까지는 3시간 이내로 배달할 수 있는 경로가 없으므로 3번 마을에서는 주문을 받지 않습니다. 따라서 1번 마을에 있는 음식점이 배달 주문을 받을 수 있는 마을은 4개가 됩니다.

마을의 개수 N, 각 마을을 연결하는 도로의 정보 road, 음식 배달이 가능한 시간 K가 매개변수로 주어질 때, 음식 주문을 받을 수 있는 마을의 개수를 return 하도록 solution 함수를 완성해주세요.

 Constraints

• 마을의 개수 N은 1 이상 50 이하의 자연수입니다.
• road의 길이(도로 정보의 개수)는 1 이상 2,000 이하입니다.
• road의 각 원소는 마을을 연결하고 있는 각 도로의 정보를 나타냅니다.
• road는 길이가 3인 배열이며, 순서대로 (a, b, c)를 나타냅니다.
  • a, b(1 ≤ a, b ≤ N, a != b)는 도로가 연결하는 두 마을의 번호이며, c(1 ≤ c ≤ 10,000, c는 자연수)는 도로를 지나는데 걸리는 시간입니다.
  • 두 마을 a, b를 연결하는 도로는 여러 개가 있을 수 있습니다.
  • 한 도로의 정보가 여러 번 중복해서 주어지지 않습니다.
• K는 음식 배달이 가능한 시간을 나타내며, 1 이상 500,000 이하입니다.
• 임의의 두 마을간에 항상 이동 가능한 경로가 존재합니다.
• 1번 마을에 있는 음식점이 K 이하의 시간에 배달이 가능한 마을의 개수를 return 하면 됩니다.

󰦕 Examples

N	road	K	result
5	[[1,2,1],[2,3,3],[5,2,2],[1,4,2],[5,3,1],[5,4,2]]	3	4
6	[[1,2,1],[1,3,2],[2,3,2],[3,4,3],[3,5,2],[3,5,3],[5,6,1]]	4	4

Solutions

󰘦 Code

import java.util.*;

class Solution {
    public int solution(int N, int[][] road, int K) {
        // 그래프를 인접 리스트로 구성하여 각 마을 간의 연결 상태를 저장
        List<List<int[]>> graph = new ArrayList<>();
        for (int i = 0; i <= N; i++) {
            graph.add(new ArrayList<>());
        }
        
        // 도로 정보를 그래프로 변환 (양방향 도로이므로 서로 연결)
        for (int[] r : road) {
            int a = r[0], b = r[1], c = r[2];   // a와 b는 마을 번호, c는 두 마을 간의 이동 시간
            graph.get(a).add(new int[]{b, c});  // 마을 a에서 b로 가는 도로 추가
            graph.get(b).add(new int[]{a, c});  // 마을 b에서 a로 가는 도로 추가
        }
        
        // 각 마을까지의 최단 거리를 저장할 배열을 초기화
        int[] dist = new int[N + 1];
        Arrays.fill(dist, Integer.MAX_VALUE);  // 모든 마을까지의 거리를 무한대로 설정
        dist[1] = 0;  // 1번 마을에서 출발하므로 1번 마을까지의 거리는 0으로 설정
        
        // 우선순위 큐를 초기화하여 다익스트라 알고리즘을 실행할 준비
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // 거리 기준으로 정렬
        pq.offer(new int[]{1, 0});  // 1번 마을에서 출발, 초기 거리는 0
        
        // 다익스트라 알고리즘을 실행하여 1번 마을에서 다른 모든 마을까지의 최단 경로를 구함
        while (!pq.isEmpty()) {
            int[] current = pq.poll();  // 큐에서 가장 짧은 경로를 가진 마을을 꺼냄
            int now = current[0];  // 현재 마을 번호
            int time = current[1];  // 현재 마을까지 걸린 시간
            
            if (time > dist[now]) continue;  // 이미 더 짧은 경로가 있다면 무시
            
            // 현재 마을에서 연결된 다른 마을로 이동
            for (int[] next : graph.get(now)) {
                int nextVillage = next[0];  // 다음 마을 번호
                int nextTime = time + next[1];  // 현재까지의 시간 + 다음 마을까지의 이동 시간
                
                // 더 짧은 경로를 발견하면 거리 갱신
                if (nextTime < dist[nextVillage]) {
                    dist[nextVillage] = nextTime;  // 최단 거리 갱신
                    pq.offer(new int[]{nextVillage, nextTime});  // 갱신된 경로를 큐에 추가
                }
            }
        }
        
        // 배달 가능한 마을의 개수를 계산 (최단 거리가 K 이하인 마을을 카운트)
        int answer = 0;
        for (int i = 1; i <= N; i++) {
            if (dist[i] <= K) answer++;  // K 시간 이내에 도달할 수 있는 마을을 찾음
        }
        
        return answer;  // 배달 가능한 마을의 개수를 반환
    }
}

 Approach

이 문제는 그래프 탐색 유형으로, 가중치가 있는 그래프에서 각 마을로 가는 최단 경로를 계산하는 문제입니다. 각 마을을 노드로, 도로를 간선으로 표현하여, 다익스트라 알고리즘(Dijkstra’s Algorithm)을 사용해 1번 마을에서 시작해 각 마을까지의 최단 경로를 구합니다. 이후, 배달 제한 시간 이내에 도달할 수 있는 마을들을 찾아내는 방식으로 문제를 해결할 수 있습니다.

1. 문제 분석

주어진 마을과 도로 정보에서 1번 마을을 출발점으로 하여, 각 마을까지의 최단 경로를 계산하고 배달이 가능한 마을의 개수를 구하는 문제입니다. 배달은 주어진 제한 시간 K 이내에 가능한 마을에서만 이루어지며, 이러한 문제는 그래프 탐색에서 최단 경로를 찾는 전형적인 유형입니다.

마을과 도로는 그래프 구조로 나타낼 수 있으며, 이때 마을은 노드, 도로는 간선으로 표현됩니다. 각 도로는 양방향으로 연결되어 있고, 도로를 지나는 데 걸리는 시간이 주어져 있으므로 가중치가 있는 그래프 문제로 접근할 수 있습니다. 주어진 제한 시간 이내로 배달이 가능한 마을을 구하는 것은, 결국 1번 마을에서 다른 마을까지의 최단 경로를 찾는 문제입니다.

이를 해결하기 위해 다익스트라 알고리즘을 사용할 수 있습니다. 다익스트라 알고리즘을 통해 1번 마을에서 각 마을까지의 최단 시간을 구할 수 있으며, 그 시간이 제한 시간 이하인 마을들을 판별할 수 있습니다.

Dijkstra’s Algorithm
다익스트라 알고리즘은 가중치가 있는 그래프에서 한 정점에서 다른 모든 정점까지의 최단 경로를 찾는 탐욕적 접근법 기반의 알고리즘입니다. 이 알고리즘은 우선순위 큐를 사용해 가장 짧은 경로부터 탐색하며, 각 정점까지의 최단 거리를 지속적으로 갱신하는 방식으로 동작합니다. 먼저, 시작 정점에서 가장 짧은 경로로 도달할 수 있는 정점을 선택하고 그 경로를 확정한 후, 해당 정점과 연결된 다른 정점들의 경로를 갱신합니다. 이를 반복하여 전체 정점의 최단 경로를 계산합니다.

따라서 문제 해결을 위해서는 먼저 도로 정보를 바탕으로 그래프를 구성한 후, 다익스트라 알고리즘을 사용해 최단 경로를 구하고, 이를 기반으로 제한 시간 내에 배달이 가능한 마을을 찾는 과정이 필요합니다.

2. 접근 방식

문제를 해결하기 위해서는 마을을 노드로, 도로를 간선으로 연결한 그래프를 구성하는 것이 첫 번째 단계입니다. 이를 통해 각 마을 간의 연결 정보를 효율적으로 저장할 수 있습니다. 이후에는 다익스트라 알고리즘을 적용하여 최단 경로를 갱신하면서 배달 가능한 마을을 찾아내는 방식으로 접근하면 됩니다.

• 그래프 구성: 주어진 도로 정보를 바탕으로 각 마을을 노드로, 두 마을 간의 연결된 도로를 간선으로 표현하는 그래프를 만듭니다. 도로는 양방향이므로 각 마을 간 이동 시간이 양방향으로 적용됩니다.
• 다익스트라 알고리즘 적용: 1번 마을을 출발점으로 설정한 뒤, 우선순위 큐를 활용해 각 마을로 가는 최단 경로를 탐색합니다. 각 단계에서 가장 짧은 경로를 가진 마을을 선택하고, 그 마을을 기준으로 다른 마을로 가는 경로를 업데이트합니다. 이 과정을 통해 각 마을까지의 최단 경로를 효율적으로 계산할 수 있습니다.
• 최단 경로 갱신: 다익스트라 알고리즘은 경로 탐색 중 더 짧은 경로가 발견될 경우, 해당 경로로 업데이트하는 방식으로 동작합니다. 이를 통해, 1번 마을에서 출발해 다른 마을로 가는 모든 경로를 효율적으로 갱신할 수 있습니다.
• 결과 도출: 최종적으로, 다익스트라 알고리즘으로 계산된 최단 경로를 바탕으로, 주어진 시간 K 내에 도달할 수 있는 마을의 개수를 계산합니다. 이때, 최단 시간이 K 이하인 마을들을 카운팅하여 최종 결과로 반환합니다.

3. 도로 기반 마을 간 그래프 구성

주어진 도로 정보를 바탕으로 마을과 도로를 연결하는 그래프를 먼저 구성해야 합니다. 마을은 노드로, 도로는 간선으로 표현하며, 도로를 지나는 데 걸리는 시간을 간선의 가중치로 사용합니다. 이때, 각 도로는 양방향으로 연결되어 있으므로, 마을 간의 이동이 양방향이라는 점을 반영하여 그래프를 구성해야 합니다.

그래프는 인접 리스트 방식으로 구현하는 것이 효율적입니다. 인접 리스트는 각 마을이 다른 마을들과 어떻게 연결되어 있는지를 저장하며, 각 마을 간의 연결 정보는 마을 번호와 이동 시간을 함께 기록합니다. 이를 위해 그래프는 List<List<int[]>> 구조로 구성되며, 각 리스트는 해당 마을과 연결된 다른 마을들의 경로 정보를 포함합니다.

여기서 경로 정보는 int[] 배열로 저장되며, 배열에는 다음과 같은 두 가지 값이 포함됩니다:

• int[0]: 연결된 마을의 번호
• int[1]: 해당 마을로 이동하는 데 걸리는 시간 (도로의 가중치)

이러한 구조를 통해 각 마을에서 다른 마을로 이동하는 경로와, 그 경로를 지나는 데 필요한 시간을 함께 저장할 수 있습니다. 예를 들어, 마을 1과 마을 2가 도로로 연결되어 있고 그 도로를 지나는 데 3분이 걸린다면, 그래프에 다음과 같이 저장됩니다:

graph.get(1).add(new int[]{2, 3});  // 마을 1에서 마을 2로 가는 도로, 3분 소요
graph.get(2).add(new int[]{1, 3});  // 마을 2에서 마을 1로 가는 도로, 3분 소요 (양방향)

graph.get(1)은 마을 1과 연결된 마을들의 리스트를 반환하며, 이 리스트에는 int[] 배열이 포함되어 있습니다. 배열의 첫 번째 값은 연결된 마을의 번호이고, 두 번째 값은 이동하는 데 걸리는 시간입니다. 즉, 위 예제에서는 마을 1에서 마을 2로 이동하는 데 3분이 걸린다는 의미입니다. 이때 도로는 양방향이므로, 마을 2에서도 마을 1로 가는 동일한 정보가 저장됩니다.

이제 이러한 정보를 기반으로 모든 마을과 도로를 연결하는 인접 리스트를 구성할 수 있습니다. 코드로 표현하면 다음과 같습니다:

List<List<int[]>> graph = new ArrayList<>();
for (int i = 0; i <= N; i++) {  // N개의 마을에 대해 인접 리스트 생성
    graph.add(new ArrayList<>());
}

// 도로 정보를 그래프로 변환 (양방향 연결)
for (int[] r : road) {
    int a = r[0], b = r[1], c = r[2];   // a와 b는 마을 번호, c는 해당 도로를 지나는 시간
    graph.get(a).add(new int[]{b, c});  // 마을 a에서 마을 b로 가는 도로와 그 시간 저장
    graph.get(b).add(new int[]{a, c});  // 마을 b에서 마을 a로 가는 도로와 그 시간 저장 (양방향)
}

이 과정을 통해, 도로 정보를 기반으로 각 마을을 노드로 하고, 도로의 시간 정보를 간선의 가중치로 저장하는 그래프 구조를 만들 수 있습니다. 이후 이 그래프를 활용해 다익스트라 알고리즘을 적용하여 각 마을까지의 최단 경로를 계산할 수 있습니다.

4. 최단 경로 탐색을 위한 자료구조 초기화

그래프 구성이 완료된 후, 최단 경로 탐색을 위해 필요한 자료구조와 변수를 초기화합니다. 이 단계에서는 각 마을까지의 최단 거리를 저장할 배열과, 경로 탐색을 위한 우선순위 큐를 준비합니다.

먼저, 각 마을까지의 최단 거리를 저장할 배열을 초기화합니다. 배열의 인덱스는 마을 번호에 대응하고, 값은 해당 마을까지의 최단 거리를 나타냅니다. 초기 상태에서는 모든 마을까지의 거리를 무한대로 설정하며, 1번 마을에서 출발하므로 1번 마을까지의 거리는 0으로 설정합니다. 이 배열은 최단 경로 탐색 과정에서 각 마을까지의 거리를 계속 갱신하며, 탐색이 완료된 후에는 이 배열에 기록된 최단 경로 정보를 사용하여 최종 결과를 산출합니다.

int[] dist = new int[N + 1];  // 각 마을까지의 최단 거리를 저장하는 배열
Arrays.fill(dist, Integer.MAX_VALUE);  // 모든 거리를 무한대로 초기화
dist[1] = 0;  // 1번 마을에서 출발하므로 1번 마을까지의 거리는 0으로 설정

다음으로, 경로 탐색을 효율적으로 진행하기 위해 거리를 기준으로 정렬되는 우선순위 큐를 초기화합니다. 큐에 저장할 원소는 [마을 번호, 해당 마을까지의 거리] 형식이며, 원소의 두 번째 값인 거리를 정렬 기준으로 활용합니다. 이렇게 정렬되도록 하면 가장 짧은 경로부터 우선적으로 처리할 수 있어 최단 경로 탐색이 더욱 효율적으로 이루어집니다.

// 다익스트라 알고리즘을 위한 우선순위 큐 초기화 (첫 번째 원소: 마을 번호, 두 번째 원소: 해당 마을까지의 거리)
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // 해당 마을까지의 거리 기준으로 정렬
pq.offer(new int[]{1, 0});  // 1번 마을에서 출발, 초기 거리는 0

5. 그래프 탐색을 통한 최단 경로 업데이트

이제, 준비한 그래프와 초기화된 큐 및 배열을 이용해 다익스트라 알고리즘을 실행하여, 1번 마을에서 각 마을까지의 최단 경로를 구합니다. 다익스트라 알고리즘은 큐에서 가장 짧은 경로로 도달할 수 있는 마을을 하나씩 꺼내고, 그 마을과 연결된 다른 마을로 이동하는 경로를 탐색하는 방식으로 진행됩니다. 이 과정을 통해 각 마을까지의 최단 경로를 지속적으로 갱신하며, 모든 마을에 대한 최단 거리를 효율적으로 계산할 수 있습니다.

주요 처리 단계는 다음과 같습니다:

1. 현재 마을에서 탐색을 시작: 큐에서 가장 짧은 경로로 도달할 수 있는 마을을 꺼내고, 해당 마을에서 다른 마을로 갈 수 있는 경로를 탐색합니다.
2. 이미 처리된 경로 확인: 현재 마을에 대한 경로가 이미 더 짧은 경로로 갱신된 경우라면, 해당 경로는 무시하고 탐색을 계속 진행합니다.
3. 최단 경로 갱신: 새로운 경로를 통해 더 짧은 시간이 발견되면, 최단 경로를 갱신하고, 갱신된 경로를 큐에 추가하여 다시 탐색을 이어나갑니다.

이 과정은 더 이상 탐색할 경로가 남아 있지 않을 때까지 반복되며, 최종적으로 모든 마을에 대한 최단 경로가 dist 배열에 저장됩니다.

while (!pq.isEmpty()) {
    int[] current = pq.poll();  // 큐에서 가장 짧은 경로를 가진 마을을 꺼냄
    int now = current[0];  // 현재 마을 번호
    int time = current[1];  // 현재 마을까지 걸린 시간
    
    if (time > dist[now]) continue;  // 이미 더 짧은 경로로 처리된 경우 무시
    
    for (int[] next : graph.get(now)) {
        int nextVillage = next[0];  // 다음 마을 번호
        int nextTime = time + next[1];  // 현재 시간 + 다음 마을까지의 이동 시간
        
        if (nextTime < dist[nextVillage]) {
            dist[nextVillage] = nextTime;  // 최단 거리 갱신
            pq.offer(new int[]{nextVillage, nextTime});  // 갱신된 경로를 큐에 추가
        }
    }
}

이처럼 각 마을의 최단 경로를 갱신하면서, 주어진 시간 내에 도달할 수 있는 마을들을 확인할 수 있게 됩니다.

6. 최종 결과 계산

다익스트라 알고리즘을 통해 각 마을까지의 최단 경로가 모두 구해진 후, 이제 배달이 가능한 마을의 개수를 계산합니다. 배달 가능한 마을은 주어진 시간 K 이내에 도달할 수 있는 마을로 제한되며, dist 배열에 저장된 각 마을까지의 최단 거리를 기준으로 K 이하인 마을들을 찾아 카운트합니다.

int answer = 0;  // 배달 가능한 마을의 개수를 저장할 변수 초기화
for (int i = 1; i <= N; i++) {
    if (dist[i] <= K) answer++;  // 최단 거리가 K 이내인 마을을 카운트
}
return answer;  // 배달 가능한 마을의 총 개수 반환

이 dist 배열의 각 인덱스는 마을 번호에 대응하며, 값은 1번 마을에서 해당 마을까지의 최단 거리를 나타냅니다. 이 배열을 순회하면서 최단 거리가 K 이하인 마을들을 찾아 카운트하고, 최종적으로 배달이 가능한 마을의 수를 반환합니다.

󰄉 Complexity

• ⏳ TC: O(E * logV)
• 💾 SC: O(V + E)

이 문제에서 시간 복잡도는 다익스트라 알고리즘의 시간 복잡도와 동일합니다. V는 마을의 개수, E는 도로의 개수로, 우선순위 큐를 사용하는 다익스트라 알고리즘의 시간 복잡도는 O(E * logV)입니다. 공간 복잡도는 마을과 도로 정보를 저장하는 데 필요한 공간으로, O(V + E)입니다.