[Java] 백준 BOJ / 1238번: 파티

파티

문제

---

문제 설명

파티에 참가하는 N 명이 목적지인 X 마을까지 왕복해야하는데 가장 오래걸리는 사람의 소요시간을 구하는 문제이다.

모든 정점에서 모든 정점까지의 거리가 아닌 각 출발지에서 하나의 정점인 X까지 가는 거리와 X에서 모든 정점까지의 거리를 구하면 되니 플로워셜 대신 다익스트라로 풀었다.

---

구현

일단 필요한 자료구조로 Edge 클래스를 선언하고 Comparable 를 구현해서 최단 거리를 구하도록 했다.

static class Edge implements Comparable<Edge> {
	int dest, weight;
    
	Edge(int dest, int weight) {
		this.dest = dest;
		this.weight = weight;
	}
    
	public int compareTo(Edge o) {
		return this.weight - o.weight;
	}
}

그리고나서 X 마을에서 집으로 돌아갈 그래프를 graph로 두고 역으로 학생 i 가 X 마을로 돌아갈 그래프를 reverseGraph로 선언한다.

정방향 그래프는 입력 그대로, 역방향 그래프는 간선을 뒤집어서 저장함으로 i -> X, X -> i 두 방향 모두의 최단 거리를 구할 수 있다.

그리고 이동 거리를 저장할 dist 배열 또한 distGo, distBack 이렇게 두개 선언한다.

graph = new ArrayList[n + 1];
reverseGraph = new ArrayList[n + 1];
distGo = new int[n + 1];
distBack = new int[n + 1];

for (int i = 1; i <= n; i++) {
	graph[i] = new ArrayList<>();
	reverseGraph[i] = new ArrayList<>();
}

for (int i = 0; i < m; i++) {
	st = new StringTokenizer(br.readLine());
	int from = Integer.parseInt(st.nextToken());
	int to = Integer.parseInt(st.nextToken());
	int time = Integer.parseInt(st.nextToken());

	graph[from].add(new Edge(to, time));
	reverseGraph[to].add(new Edge(from, time));
}

이제 위에서 Edge를 구현한 대로 PriorityQueue를 사용하여 최단거리를 최신화 해주게 다익스트라를 구현하면 된다.

---

코드

import java.util.*;
import java.io.*;

public class Main_1238 {
    static int n, m, x;
    static ArrayList<Edge>[] graph;
    static ArrayList<Edge>[] reverseGraph;
    static int[] distGo, distBack;
    static final int INF = 100000000;

    static class Edge implements Comparable<Edge> {
        int dest, weight;
        Edge(int dest, int weight) {
            this.dest = dest;
            this.weight = weight;
        }
        public int compareTo(Edge o) {
            return this.weight - o.weight;
        }
    }

    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];
        reverseGraph = new ArrayList[n + 1];
        distGo = new int[n + 1];
        distBack = new int[n + 1];

        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
            reverseGraph[i] = new ArrayList<>();
        }

        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int time = Integer.parseInt(st.nextToken());

            graph[from].add(new Edge(to, time));
            reverseGraph[to].add(new Edge(from, time));
        }

        distGo = dijkstra(reverseGraph, x);
        distBack = dijkstra(graph, x);

        int maxTime = 0;
        for (int i = 1; i <= n; i++) {
            maxTime = Math.max(maxTime, distGo[i] + distBack[i]);
        }

        System.out.println(maxTime);
    }

    static int[] dijkstra(ArrayList<Edge>[] edge, int start) {
        int[] dist = new int[n + 1];
        Arrays.fill(dist, INF);
        PriorityQueue<Edge> pq = new PriorityQueue<>();
        pq.add(new Edge(start, 0));
        dist[start] = 0;

        while (!pq.isEmpty()) {
            Edge cur = pq.poll();
            if (dist[cur.dest] < cur.weight) continue;

            for (Edge next : edge[cur.dest]) {
                int nextDist = cur.weight + next.weight;
                if (dist[next.dest] > nextDist) {
                    dist[next.dest] = nextDist;
                    pq.add(new Edge(next.dest, nextDist));
                }
            }
        }
        return dist;
    }
}