[백준 / JAVA] 1238번 파티

Hanul Jeong·2024년 8월 12일

Java 백준

코딩 테스트

목록 보기

8/8

문제

https://www.acmicpc.net/problem/1238

접근

방향 그래프에서 최단 경로를 구하는 문제이다.

그래프 최단 경로 알고리즘

다익스트라 알고리즘
벨만-포드 알고리즘
플로이드-워셜 알고리즘

크게 3가지가 있는데, 문제에서 도로를 지나는데 필요한 소요시간(Ti)의 범위가 양수이기 때문에 필자는 다익스트라 알고리즘을 선택했다.

다익스트라 알고리즘을 사용하여 각 마을마다 최단 거리 배열을 채우고, 이 N개의 배열을 참고하여 각 학생들의 소요시간을 구한다.

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class boj_1238 {
    //public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        int x = Integer.parseInt(st.nextToken());

        int[][] distance = new int[n + 1][n + 1];
        for (int i = 1; i < n + 1; i++)
            Arrays.fill(distance[i], Integer.MAX_VALUE);

        ArrayList<ArrayList<Node>> graph = new ArrayList<>();
        for (int i = 0; i < n + 1; i++) {
            graph.add(new ArrayList<>());
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int t = Integer.parseInt(st.nextToken());

            graph.get(s).add(new Node(e, t));
        }

        for (int i = 1; i < n + 1; i++) {
            boolean[] visited = new boolean[n + 1];
            dijkstra(i, graph, distance[i], visited, n);
        }

        int output = Integer.MIN_VALUE;
        for (int i = 1; i < n + 1; i++) {
            if (distance[i][x] + distance[x][i] > output) output = distance[i][x] + distance[x][i];
        }

        System.out.println(output);
    }

    static void dijkstra(int start, ArrayList<ArrayList<Node>> graph, int[] distance, boolean[] visited, int n) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.weight));
        pq.offer(new Node(start, 0));
        distance[start] = 0;

        while (!pq.isEmpty()) {
            Node k = pq.poll();
            int currentNode = k.destination;

            if (visited[currentNode]) continue;
            visited[currentNode] = true;

            ArrayList<Node> list = graph.get(currentNode);
            for (int i = 0; i < list.size(); i++) {
                Node node = list.get(i);

                if (distance[currentNode] + node.weight < distance[node.destination]) {
                    distance[node.destination] = distance[currentNode] + node.weight;
                    pq.offer(new Node(node.destination, distance[node.destination]));
                }
            }
        }
    }

    static class Node {
        int destination;
        int weight;

        Node(int node, int weight) {
            this.destination = node;
            this.weight = weight;
        }
    }
}

정리

다익스트라 알고리즘은 이론으로만 알고 있었고 풀이에서 한 번도 사용한 적이 없어 구현할 때 어려움이 있었다.

`dijkstra()` 에서 다음 노드 선택

처음엔 모든 노드를 비교하여 최소 거리 값의 노드를 구하는 방식으로 구현했다.

	static void dijkstra(int start, ArrayList<ArrayList<Node>> graph, int[] distance, boolean[] visited, int n) {
        distance[start] = 0;

        int currentNode = start;
        for (int i = 0; i < n; i++) {
            int minDistance = Integer.MAX_VALUE;
            for (int j = 1; j < n + 1; j++) {
                if (!visited[j] && distance[j] < minDistance) {
                    currentNode = j;
                    minDistance = distance[j];
                }
            }

            visited[currentNode] = true;
            for (int j = 0; j < graph.get(currentNode).size(); j++) {
                Node node = graph.get(currentNode).get(j);

                if (distance[currentNode] + node.weight < distance[node.destination])
                    distance[node.destination] = distance[currentNode] + node.weight;
            }
        }
    }

하지만, 이 경우에는 모든 노드의 최단 거리를 비교해야 하기 때문에 비교적 느리다. -> 우선 순위 큐를 사용하여 시간복잡도를 줄일 수 있다.

    static void dijkstra(int start, ArrayList<ArrayList<Node>> graph, int[] distance, boolean[] visited, int n) {
        PriorityQueue<Node> pq = new PriorityQueue<>(Comparator.comparingInt(a -> a.weight));
        pq.offer(new Node(start, 0));
        distance[start] = 0;

        while (!pq.isEmpty()) {
            Node k = pq.poll();
            int currentNode = k.destination;

            if (visited[currentNode]) continue;
            visited[currentNode] = true;

            ArrayList<Node> list = graph.get(currentNode);
            for (int i = 0; i < list.size(); i++) {
                Node node = list.get(i);

                if (distance[currentNode] + node.weight < distance[node.destination]) {
                    distance[node.destination] = distance[currentNode] + node.weight;
                    pq.offer(new Node(node.destination, distance[node.destination]));
                }
            }
        }
    }