[백준][BOJ-1238][JAVA] 파티

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

1238번: 파티

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

public class Main {
	int N, M, X;
	int[][] map;
	final int INFINITY = Integer.MAX_VALUE;

	private void solution() 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());
		map = new int[N+1][N+1];
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int time = Integer.parseInt(st.nextToken());
			
			map[start][end] = time;
		}
		
		int[] result = new int[N+1];
		
		for(int i=1; i<=N; i++) {
			result[i] = dijkstra(i, X) + dijkstra(X, i);
		}
		
		System.out.println(Arrays.stream(result).max().getAsInt());
	}
	
	private int dijkstra(int start, int end) {
		PriorityQueue<Vertex> pQueue = new PriorityQueue<Vertex>();
		boolean[] visited = new boolean[N+1];
		int[] distance = new int[N+1];
		
		Arrays.fill(distance, INFINITY);
		distance[start] = 0;
		
		pQueue.offer(new Vertex(start, distance[start]));
		
		Vertex curr = null;
		
		while(!pQueue.isEmpty()) {
			curr = pQueue.poll();
			
			if(curr.no == end) break;
			
			if(visited[curr.no]) continue;
			visited[curr.no] = true;
			
			for(int i=1; i<=N; i++) {
				if(!visited[i] && map[curr.no][i] !=0
						&& distance[i] > curr.totalDistance + map[curr.no][i]) {
					distance[i] = curr.totalDistance + map[curr.no][i];
					pQueue.offer(new Vertex(i, distance[i]));
				}
			}
		}
		
		return distance[end];
	}

	public static void main(String[] args) throws IOException{
		new Main().solution();		
	}
}

class Vertex implements Comparable<Vertex>{
	int no;
	int totalDistance;
	
	public Vertex(int no, int totalDistance) {
		super();
		this.no = no;
		this.totalDistance = totalDistance;
	}

	@Override
	public int compareTo(Vertex o) {
		return this.totalDistance - o.totalDistance;
	}
}

정리

시작점이 주어지고 도착점 또한 주어진다. 그다음 최단 시간을 구하기 때문에 다익스트라로 풀면 좋겠다고 생각하였다.

https://gooweon.tistory.com/67?category=1195305 

다익스트라 알고리즘(Dijkstra Algorithm)

하지만 문제 상에서 각 시작점이 틀려지기 때문에 반복문으로 각 정점마다 시작점을 다르게 해서 최단 시간을 받았다. 그와 반대로 도착점에서 다시 시작점으로 돌아가야 되기 때문에 start와 end의 파라미터를 반대로 넣어줘서 값을 받아서 두 값을 더하여 result 배열에 저장해 두었다가 출력에서 요구한 가장 오래 걸리는 학생의 소요시간을 출력해주었다.