[백준] 파티 1238 [JAVA]

출처 : www.acmicpc.net/problem/1238

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

풀이방법

1. 다익스트라, 크루스칼, 프림 등 최단 거리 알고리즘을 떠올렸지만 목적지 까지 최단거리를 구한 후에 다시 원래의 도시까지 오는 최단 거리를 구하는 방법이 도저히 떠오르지 않았다. ==> 자료를 참고하게 됨 .ㅠ

2. 다익스트라를 2번 사용함으로써 해결할 수 있었다.

3. 결과론적으로 보면, 각 마을에서 X 까지 가는 최단거리 + X에서 각 마을 까지 오는 최단거리 의 합중 최대를 구하는것

4. 다익스트라를 이용하기위해 저장하는 방법을 조금 바꿔보자.

5. 각 마을에서 X 까지 가는 최단거리 = 문제에서 주어지는 from => to , weight 에서 to => from 으로 바꾸어 간선을 저장한다. 
   ex. 1 -> 2 -> 3 ( 1 -> 3 까지 도착하는 거리는 ) - 거리의 합 값만 보자 ( 결국 1, + 2, +  3 )
       3 -> 2 -> 1 ( 3 -> 1 까지 도착하는 거리로 나타낼 수 있다. ) - 거리의 합 값만 보자 ( 결국 3 + 2+ 1 ) 같다.

6.  X에서 각 마을 까지 오는 최단거리 = 문제에서 주어지는 from -> to 간선을 활용하되, 시작점을 X로 처리 

 

package 알고리즘스터디;

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

public class 파티_1238 {

	static int N, M, X, INF = Integer.MAX_VALUE;
	static int[] dist; // X -> 각 마을
	static int[] rdist; // 각 마을 -> X로 가는
	static List<List<Node>> arr, Rarr; // 리스트로 간선 관리

	private static class Node implements Comparable<Node> {
		int N;
		int weight;

		private Node(int target, int weight) {
			this.N = target;
			this.weight = weight;
		}

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

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		// input
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken()); // 마을의 수
		M = Integer.parseInt(st.nextToken()); // 간선의 개수
		X = Integer.parseInt(st.nextToken()); // 목적지 X

		// init
		dist = new int[N + 1]; // 1부터 시작
		rdist = new int[N + 1]; // 1부터 시작

		arr = new ArrayList<>();
		Rarr = new ArrayList<>();
		for (int i = 0; i < N + 1; i++) {
			arr.add(new ArrayList<Node>());
			Rarr.add(new ArrayList<Node>()); // 0은 사용하지 말 것
		}

		for (int i = 1; i < N + 1; i++) {
			Arrays.fill(dist, INF);
			Arrays.fill(rdist, INF);
		}

		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 weight = Integer.parseInt(st.nextToken());

			arr.get(from).add(new Node(to, weight));
			Rarr.get(to).add(new Node(from, weight));
		}

		// 1. X 마을에서 출발해서 각 마을로 가는 최단 거리 배열 저장
		dijkstra();

		// 2. 주어진 간선을 역방향으로 바꾸어, X마을로 출발해서 각 마을로 가는 최단 거리 배열 저장 ( 각 마을 -> X )
		// 2-1. 모든 마을에서 X 마을 까지 다익스트라 구하는것보다 매우 효과적이다.
		Rdijkstra();
		
		int max = Integer.MIN_VALUE;
		for( int i=1; i<=N; i++	) {
			if ( max < dist[i] + rdist[i]) {
				max = dist[i] + rdist[i];
			}
		}

		// 3. 두 거리의 합중 최대를 구하면된다.
		System.out.println(max);
	}

	// X -> 각 마을로 ( arr, dist 중심 )
	private static void dijkstra() {

		PriorityQueue<Node> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[N + 1];

		dist[X] = 0;
		pq.add(new Node(X, 0)); // 처음시작점

		while (!pq.isEmpty()) {

			Node cur = pq.poll();

			if (visited[cur.N])
				continue;
			visited[cur.N] = true;

			// 해당 점으로 부터 연결된 모든 곳 탐색하기
			for (Node target : arr.get(cur.N)) {

				if (dist[target.N] > dist[cur.N] + target.weight) {
					dist[target.N] = dist[cur.N] + target.weight;
					pq.add(new Node(target.N, dist[target.N]));
				}
			}

		}
	}

	// 마을 -> X 까지 걸리는 최단 거리를 역방향으로 해결 ( Rarr, rdist 중심 )
	private static void Rdijkstra() {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		boolean[] visited = new boolean[N + 1];

		rdist[X] = 0;
		pq.add(new Node(X, 0));

		while (!pq.isEmpty()) {

			Node cur = pq.poll();

			if (visited[cur.N])
				continue;
			visited[cur.N] = true;
			// 해당 점으로 부터 연결된 모든 곳 탐색하기
			for (Node target : Rarr.get(cur.N)) {

				if (rdist[target.N] > rdist[cur.N] + target.weight) {
					rdist[target.N] = rdist[cur.N] + target.weight;
					pq.add(new Node(target.N, rdist[target.N]));
				}
			}
		}

	}

}