[백준 알고리즘] 1238번 파티(Java) 문제 풀이

문제

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

1238번: 파티

어떻게 풀 것인가?

문제를 최단경로라는 키워드를 발견 다익스트라 알고리즘이라고 생각했다.

다만 해당 N명의 인원들이 X라는 목적지 파티까지 가는 경로의 최단경로와 그리고 X에서 N명의 인원들이 집까지 가는 최단경로를 구한이후 그 중에 가장큰 거리를 출력해야한다.

풀면서 놓쳤던점

다익스트라에 대한 이해가 부족해서 아래와 같은 블로그를 참고하였다.

나중에 시간이 된다면 다익스트라 알고리즘을 정리해야할 것 같다.

https://velog.io/@suk13574/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98Java%EB%8B%A4%EC%9D%B5%EC%8A%A4%ED%8A%B8%EB%9D%BCDijkstra-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98

[알고리즘/Java]다익스트라(Dijkstra) 알고리즘

이 문제를 통해 얻어갈 것

다익스트라 알고리즘

내 코드 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

// 백준알고리즘 1238번 파티

public class Main {
    static int N, M, X;
    static ArrayList<Node>[] graph;
    static int[] result;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        X = Integer.parseInt(st.nextToken());
        graph = new ArrayList[N + 1];
        result = new int[N + 1];
        for (int i = 0; i <= N; i++) graph[i] = new ArrayList<>();

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            int v = Integer.parseInt(st.nextToken());
            int w = Integer.parseInt(st.nextToken());
            int cost = Integer.parseInt(st.nextToken());
            graph[v].add(new Node(w, cost));
        }
        for (int i = 1; i <= N; i++) {
            goParty(N, i);
        }
        goHome(N, X);

        int max = -2147000000;
        for (int i = 0; i <= N; i++) {
            if (result[i] > max) {
                max = result[i];
            }
        }
        System.out.println(max);
    }

    private static void goParty(int n, int start) {
        boolean[] check = new boolean[n + 1];
        int[] dist = new int[n + 1];
        int INF = Integer.MAX_VALUE;

        Arrays.fill(dist, INF);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            int nowVertex = pq.poll().index;

            if (check[nowVertex]) continue;
            check[nowVertex] = true;

            //index의 연결된 정점 비교
            for (Node next : graph[nowVertex]) {
                if (dist[next.index] > dist[nowVertex] + next.cost) {
                    dist[next.index] = dist[nowVertex] + next.cost;

                    pq.offer(new Node(next.index, dist[next.index]));
                }
            }
        }

        //최소거리 출력
        for (int i = 0; i <= N; i++) {
            if (i == X) {
                result[start] += dist[i];
            }
        }
    }

    private static void goHome(int n, int start) {
        boolean[] check = new boolean[n + 1];
        int[] dist = new int[n + 1];
        int INF = Integer.MAX_VALUE;

        Arrays.fill(dist, INF);
        dist[start] = 0;

        PriorityQueue<Node> pq = new PriorityQueue<>();
        pq.offer(new Node(start, 0));

        while (!pq.isEmpty()) {
            int nowVertex = pq.poll().index;

            if (check[nowVertex]) continue;
            check[nowVertex] = true;

            //index의 연결된 정점 비교
            for (Node next : graph[nowVertex]) {
                if (dist[next.index] > dist[nowVertex] + next.cost) {
                    dist[next.index] = dist[nowVertex] + next.cost;

                    pq.offer(new Node(next.index, dist[next.index]));
                }
            }
        }

        //최소거리 출력
        for (int i = 0; i <= N; i++) {
            if (dist[i] == INF) result[i] += 0;
            else result[i] += dist[i];
        }
    }
}

class Node implements Comparable<Node> {
    int index;
    int cost;

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

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