[백준] 1238번 : 파티 - 자바(JAVA)

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

1238번: 파티

 

문제 해석

N명의 학생이 X번 마을에 모여서 파티를 벌이기로 했다.

마을 사이에는 총 M개의 단방향 도루들이 있고, i번째 길을 지나는데 T(i)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다.

이때 최단거리를 원하며 도로들은 단방향이다.

N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은?

 

문제 풀이 전 설계

모든 학생들은 집에서 X로 갈 수 있고 X에서 집으로 돌아올 수 있다.

집 -> X 다익스트라 1번

X -> 집 다익스트라 1번

이때 최대값을 가지는 학생을 찾아 소요시간을 출력합니다.

 

메모리제한이 128MB이므로 인접리스트로 구현합니다.

 

코드

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

public class Main_1238_파티 {

	static class Node {
		int to;
		int weight;

		public Node(int to, int weight) {
			super();
			this.to = to;
			this.weight = weight;
		}

	}

	static List<ArrayList<Node>> nodes = new ArrayList<ArrayList<Node>>();
	static int result = Integer.MIN_VALUE;
	static int[] DP;
	static boolean[] visited;
	static int N, M, X;

	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());

		DP = new int[N + 1];

		for (int i = 0; i <= N; i++) {
			nodes.add(new ArrayList<Node>());
		}

		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());
			nodes.get(from).add(new Node(to, weight));
		}

		// 학생 한명씩 DP시작
		for (int i = 1; i < N + 1; i++) {
			int tempSum = 0;

			initDP(i);
			initVisited();
			goParty();
			tempSum = DP[X];

			initDP(X);
			initVisited();
			goHome();
			tempSum += DP[i];
			result = Math.max(result, tempSum);
		}

		System.out.println(result);
	}

	private static void goParty() {
		dijkstra();
	}

	private static void goHome() {
		dijkstra();
	}

	private static void dijkstra() {
		// 방문되지 않고 가장 작은 정점 탐색
		int tempValue = Integer.MAX_VALUE;
		int currentIndex = 0;
		for (int i = 1; i < N + 1; i++) {

			if (visited[i]) {
				continue;
			}

			if (tempValue > DP[i]) {
				tempValue = DP[i];
				currentIndex = i;
			}
		}
		// 방문 체크
		visited[currentIndex] = true;

		// 만약 모두 방문되었거나 방문가능한 정점이 존재하지 않으면 종료
		if (tempValue == Integer.MAX_VALUE) {
			return;
		}

		// 현재 정점기준으로 최단거리(DP) 배열 갱신
		for (Node e : nodes.get(currentIndex)) {
			DP[e.to] = Math.min(DP[e.to], DP[currentIndex] + e.weight);
		}
		dijkstra();
	}

	static void initDP(int startLocation) {
		// i번째 마을에 사는 친구를 위한 DP배열 초기화
		// DP[i] = 0 , 나머지 = MAX_VALUE

		for (int i = 0; i < DP.length; i++) {
			DP[i] = Integer.MAX_VALUE;
		}
		DP[startLocation] = 0;
	}

	static void initVisited() {
		visited = new boolean[N + 1];
	}
}