2020년 마지막날에도 문제풀이,,,🔥 신난다 ~

문제링크

백준 #1753. 최단경로

풀이방법

아주아주 대표적인 다익스트라 알고리즘 문제입니다!

다익스트라 알고리즘은 그래프의 한 정점에서 시작해 다른 정점들로의 최단거리를 구하는 알고리즘입니다. 다음 방법으로 최단거리 탐색을 진행합니다~

step1. 아직 방문하지 않은 정점 중 거리가 가장 짧은 하나를 선택, 방문
step2. 해당 정점에 인접하고아직 방문하지 않은 정점들의 거리 계산, 가장 짧은 거리로 갱신
위 과정을 모든 정점을 방문할때까지 반복!

호호 쉽죠?

자료구조

두 가지 자료구조를 사용했는데요, 각 자료구조를 선택한 이유를 설명하겠습니다.

우선순위큐

step1. 아직 방문하지 않은 정점 중 거리가 가장 짧은 하나를 선택, 방문

이 단계 구현을 우선순위큐를 사용했습니다! 계속 값이 갱신되고 매번 최소값을 찾아야하는 상황이라 반정렬상태인 우선순위큐가 적합한 자료구조라고 판단했습니다.

링크드리스트

두 간선 사이의 cost를 저장하는 costs 변수를 처음에는 아무 생각없이 2차원 배열로 구현했는데요, 제출 시 메모리초과가 떳습니다 ㅋ ㅋ
costs 접근시에도 순차적으로 접근하기 때문에 링크드리스트가 적합하다고 생각해 이용했습니다~

코드

import java.util.LinkedList;
import java.util.PriorityQueue;
import java.util.Scanner;

public class ShortestPath {
    static LinkedList<Node>[] costs;
    static boolean[] visited;
    static PriorityQueue<Node> pq = new PriorityQueue<>();
    static int[] dist;

    static int v;
    static public void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        v = sc.nextInt(); // 1 ~ v
        int e = sc.nextInt();
        int k = sc.nextInt();
        initVariables();

        for (int i = 0; i < e; i++) {
            int sourceNode = sc.nextInt();
            int destinationNode = sc.nextInt();
            int cost = sc.nextInt();

            costs[sourceNode].add(new Node(destinationNode, cost)); // cost as a weight from source to dest
        }

        dist[k] = 0;
        pq = new PriorityQueue<>(); // cost as a dist from k
        pq.add(new Node(k, dist[0]));

        while (!pq.isEmpty()) {
            Node headNode = pq.poll();
            if (!visited[headNode.nodeId]) updatePath(headNode.nodeId);
        }

        StringBuilder result = new StringBuilder();
        for (int i = 1; i <= v; i++) {
            if (dist[i] != Integer.MAX_VALUE) result.append(dist[i] + "\n");
            else result.append("INF\n");
        }
        System.out.print(result);
    }

    static private void initVariables() {
        visited = new boolean[v + 1];

        costs = new LinkedList[v + 1];
        for (int i = 1; i <= v; i++) costs[i] = new LinkedList<>();

        dist = new int[v + 1];
        for (int i = 1; i <= v; i++) dist[i] = Integer.MAX_VALUE;
    }

    static private void updatePath(int headNode) {
        visited[headNode] = true;

        // 두 정점 사이에 여러 간선이 존재할 수 있음!
        for (Node node: costs[headNode]) {
            int newPathCost = dist[headNode] + node.cost;
            if (newPathCost < dist[node.nodeId]) { // 여러 간선 존재 시, 가중치가 작은걸로 갱신
                dist[node.nodeId] = newPathCost;
                pq.add(new Node(node.nodeId, dist[node.nodeId]));
            }
        }
    }
}

class Node implements Comparable<Node> {
    public int nodeId;
    public int cost;

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

    @Override
    public int compareTo(Node o) { return this.cost - o.cost; }
}