[Baekjoon] 1238_파티

Gold III

문제(출처: https://www.acmicpc.net/problem/1238)

---

< 파티 >

 

문제 풀이 

 

데이크스트라 알고리즘을 사용해서 먼저 n번째 마을에서 x번째 마을로 가는 최단 시간을 구한다. 그 후에 다시 x번째 마을에서 n번째 마을로 가는 최단 시간을 구한다.

 

 my solution (Java)

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

public class _1238_ { // 파티

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

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

		ArrayList<ArrayList<int[]>> list = new ArrayList<>();
		for (int i = 0; i < n + 1; i++) {
			list.add(new ArrayList<>());
		}

		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(bf.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int t = Integer.parseInt(st.nextToken());

			list.get(start).add(new int[] { end, t });
		}

		PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {

			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[1] - o2[1];
			}
		});

		int answer = 0;

		for (int i = 1; i <= n; i++) {
			int arr[] = new int[n + 1];
			int result[] = new int[n + 1];

			for (int j = 1; j < n + 1; j++) {
				arr[j] = Integer.MAX_VALUE;
				result[j] = Integer.MAX_VALUE;
			}

			if (i == x) {
				continue;
			}

			arr[i] = 0;
			queue.add(new int[] { i, 0 });

			while (!queue.isEmpty()) {
				int num[] = queue.poll();
				for (int j = 0; j < list.get(num[0]).size(); j++) {
					if (arr[list.get(num[0]).get(j)[0]] > num[1] + list.get(num[0]).get(j)[1]) {
						arr[list.get(num[0]).get(j)[0]] = num[1] + list.get(num[0]).get(j)[1];
						queue.add(new int[] { list.get(num[0]).get(j)[0], num[1] + list.get(num[0]).get(j)[1] });
					}
				}
			}

			result[x] = arr[x];
			queue.add(new int[] { x, result[x] });
			while (!queue.isEmpty()) {
				int num[] = queue.poll();
				for (int j = 0; j < list.get(num[0]).size(); j++) {
					if (result[list.get(num[0]).get(j)[0]] > num[1] + list.get(num[0]).get(j)[1]) {
						result[list.get(num[0]).get(j)[0]] = num[1] + list.get(num[0]).get(j)[1];
						queue.add(new int[] { list.get(num[0]).get(j)[0], num[1] + list.get(num[0]).get(j)[1] });
					}
				}
			}

			if (answer < result[i]) {
				answer = result[i];
			}
		}
		System.out.println(answer);
	}
}

변수)
n, m, x : 학생 수, 단방향 도로 개수, 파티하는 마을
list : 각 마을에 연결된 도로
start, end, t : 시작점, 끝점, 필요한 소요 시간
queue : 우선순위 큐 [마을 번호, 시간]
answer : 오고 가는데 가장 오래 걸리는 학생의 소요 시간
arr : n번째 마을 -> x번째 마을 최단 시간
result : x번째 마을 -> n번째 마을 최단 시간

 

도로의 시작점, 끝점, 이 도로를 지나는데 필요한 소요 시간을 입력받아 ArrayList를 사용해서 그래프를 만든다. 모든 학생이 x에 갔다가 집으로 돌아오는 시간을 구해야 하므로 한 명씩 다 최단 시간을 구하도록 한다.

 

먼저 배열을 Integer.MAX_VALUE로 초기화한다. x번 마을에 있는 학생을 최단 시간을 구할 필요 없으므로 넘어간다. i번째 학생이 x번 마을로 가는데 최단 시간을 구한다. 그 후 x번 마을에서 i번 마을로 돌아가는 최단 시간을 구한다. i번 마을로 돌아온 값 중에서 가장 큰 값을 구한다.

---

---