[PCCP] Lv2: 배달(12978) 해설

문제

- 문제 링크: 배달

 

해설

- 자료구조: 

- 시간복잡도: 

 

(풀이과정)

1) 

2) 

3) 

4) 

 

코드

(C언어)

solution 1)

solution 1

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C++)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(C#)

solution 1)

#include<>

solution 2)

#include<>

solution 3)

#include<>

 

(Java)

solution 1)

- E: road의 길이

- 그래프를 추가할 때 시간 복잡도는 O(E)

- 다익스트라 알고리즘은 우선순위 큐를 활용했으므로 O((N + E)logN)

- 마지막 결과 리스트를 순회하며 K 이하의 거리를 세는 연산: O(N)

- 최종 시간 복잡도: O((N + E)logN)

import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;

public class Solution {

    private static class Node {
        int dest, cost;

        public Node(int dest, int cost) {
            this.dest = dest;
            this.cost = cost;
        }
    }

    public int solution(int N, int[][] road, int K) {
        // 인접 리스트를 저장할 ArrayList 배열 초기화
        ArrayList<Node>[] adjList = new ArrayList[N + 1];
        for (int i = 1; i <= N; i++) {
            adjList[i] = new ArrayList<>();
        }

        // road 정보를 인접 리스트로 저장
        for (int[] edge : road) {
            adjList[edge[0]].add(new Node(edge[1], edge[2]));
            adjList[edge[1]].add(new Node(edge[0], edge[2]));
        }

        int[] dist = new int[N + 1];
        // 모든 노드의 거리 값을 무한대로 초기화
        Arrays.fill(dist, Integer.MAX_VALUE);

        // 우선순위 큐를 생성하고 시작 노드를 삽입
        PriorityQueue<Node> pq = new PriorityQueue<>((o1, o2) -> Integer.compare(o1.cost, o2.cost));
        pq.add(new Node(1, 0));
        dist[1] = 0;

        while (!pq.isEmpty()) {
            Node now = pq.poll();

            if (dist[now.dest] < now.cost)
                continue;

            // 인접한 노드들의 최단 거리를 갱신하고 우선순위 큐에 추가
            for (Node next : adjList[now.dest]) {
                if (dist[next.dest] > now.cost + next.cost) {
                    dist[next.dest] = now.cost + next.cost;
                    pq.add(new Node(next.dest, dist[next.dest]));
                }
            }
        }

        int answer = 0;

        // dist 배열에서 K 이하인 값의 개수를 구하여 반환
        for (int i = 1; i <= N; i++) {
            if (dist[i] <= K) answer++;
        }

        return answer;
    }

}

solution 2)

#include<>

solution 3)

#include<>

 

(Python)

solution 1)

- E: road의 길이

- 그래프를 추가: O(E)

- 다익스트라 알고리즘은 heapq를 활용했으므로 O((N + E)logN)

- 마지막 결과 리스트를 순회하며 K 이하의 거리를 세는 연산은 O(N)

- 최종 시간 복잡도: O((N + E)logN)

import heapq

def solution(N, road, K):
    # 각 노드에 연결된 간선들을 저장할 리스트
    graph = [[] for _ in range(N + 1)]
    # 출발점에서 각 노드까지의 최단 거리를 저장할 리스트
    distances = [float("inf")] * (N + 1)
    distances[1] = 0 # 출발점은 0으로 초기화
    
    # 그래프 구성
    for a, b, cost in road:
        graph[a].append((b, cost))
        graph[b].append((a, cost))
        
    # 다익스트라 알고리즘 시작
    heap = []
    heapq.heappush(heap, (0, 1)) # 출발점을 heap에 추가
    while heap:
        dist, node = heapq.heappop(heap)
        
        # 인접한 노드들의 최단 거리를 갱신하고 heap에 추가
        for next_node, next_dist in graph[node]:
            cost = dist + next_dist
            if cost < distances[next_node]:
                distances[next_node] = cost
                heapq.heappush(heap, (cost, next_node))
                
    # distances 리스트에서 K 이하인 값의 개수를 구하여 반환
    return sum(1 for dist in distances if dist <= K)

solution 2)

import

solution 3)

import

 

(JavaScript)

solution 1)

- E: road의 길이

- 그래프를 추가: O(E)

- 다익스트라 알고리즘은 heapq를 활용하였으므로 O((N + E)logN)

- 마지막 결과 배열을 순회하며 K이하의 거리를 세는 연산: O(N)

- 최종 시간 복잡도: O((N + E)logN)

class MinHeap {
    constructor() {
        this.items = [];
    }
    
    size() {
        return this.items.length;
    }
    
    insert(item) {
        this.items.push(item);
        this.bubbleUp();
    }
    
    pop() {
        if (this.size() === 0) {
            return null;
        }
        
        const min = this.items[0];
        this.items[0] = this.items[this.size() - 1];
        this.items.pop();
        this.bubbleDown();
        return min;
    }
    
    swap(a, b) {
        [this.items[a], this.items[b]] = [this.items[b], this.items[a]];
    }
    
    bubbleUp() {
        let index = this.size() - 1;
        
        while (index > 0) {
            const parentIndex = Math.floor((index - 1) / 2);
            if (this.items[parentIndex] <= this.items[index]) {
                break;
            }
            this.swap(index, parentIndex);
            index = parentIndex;
        }
    }
    
    bubbleDown() {
        let index = 0;
        while (index * 2 + 1 < this.size()) {
            let leftChild = index * 2 + 1;
            let rightChild = index * 2 + 2;
            let smallerChild = rightChild < this.size() &&
                this.items[rightChild] < this.items[leftChild]
                ? rightChild
                : leftChild
            if (this.items[index] <= this.items[smallerChild]) {
                break;
            }
            
            this.swap(index, smallerChild);
            index = smallerChild;
        }
    }
}

function solution(N, road, K) {
    // 각 노드에 연결된 간선들을 저장할 배열
    const graph = Array.from({length : N + 1}, () => []);
    // 출발점에서 각 노드까지의 최단 거리를 저장할 배열
    const distances = Array(N + 1).fill(Infinity);
    distances[1] = 0; // 출발점은 0으로 초기화
    
    // 그래프 구성
    for (const [a, b, cost] of road) {
        graph[a].push([b, cost]);
        graph[b].push([a, cost])
    }
    
    // 다익스트라 알고리즘 시작
    const heap = new MinHeap();
    heap.insert([0, 1]); // 출발점을 heap에 추가
    while (heap.size() > 0) {
        const [dist, node] = heap.pop();
        
        // 인접한 노드들의 최단 거리를 갱신하고 heap에 추가
        for (const [nextNode, nextDist] of graph[node]) {
            const cost = dist + nextDist;
            if (cost < distances[nextNode]) {
                distances[nextNode] = cost;
                heap.insert([cost, nextNode]);
            }
        }
    }
    
    // distances 배열에서 K 이하인 값의 개수를 구하여 반환
    return distances.filter((dist) => dist <= K).length;
}

solution 2)

import

solution 3)

import