[백준BOJ] 1238번 파티.java

 

백준 저지에서 파티를 자바를 통해 풀어 보았다. 

 

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

1238번: 파티

 

1238번 파티.java

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

1238번 파티

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.
어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.
각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.
이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

설명

N개의 마을이 있고 M개의 단방향 길이 있다. 이를 통해 그래프를 생성한다.

 

X번 마을에서 파티가 열리며 X번을 제외한 N-1개의 마을에서 X번 마을로 오고 간다. 이 때 가장 큰 비용을 가지는 학생의 비용을 출력하면 된다. 

 

중요한 것은 오고 가는 비용이며 단방향 그래프이므로 오고 가는 길의 비용이 다를 수 있다. 즉 A번 마을이 존재한다면 A->X 비용과 X->A 비용을 따로 구해서 더해줘야한다.

 

비용을 구하는 방법은 다익스트라 알고리즘을 사용했다.

 

가는 길을 구할 때는 X번 마을을 제외한 "?->X" 비용을 구하기위해 N-1번만큼 다익스트라를 돌렸다.

오는 길을 구할 때는 "X->?" 비용을 구하기 위해 출발점을 X로 두어서 1번만큼 다익스트라를 돌렸다.

 

총 N번의 다익스트라를 사용하여 오고 가는 길의 비용을 구하고 그 중 최댓값을 출력한다.

 

추가로 다익스트라를 사용할 때 비용을 저장하는 배열에서 최초에 비용으로 올 수 있는 최댓값보다 큰 수를 넣어야한다. 비용의 최댓값은 100이고 길의 개수 M의 최댓값은 10000이므로 둘을 곱하고 1을 더한 1000001으로 초기화했다.

코드

//1238번 파티.java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 파티_1238 {
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static StringBuilder sb = new StringBuilder();
    static final int maxNum = 1000001;
	public static void main(String[] args) throws IOException {
		st = new StringTokenizer(br.readLine()," ");
		int N = Integer.parseInt(st.nextToken());//N명의 마을
		int M = Integer.parseInt(st.nextToken());//M개의 단방향도로
		int X = Integer.parseInt(st.nextToken());//모이는 마을 X - X번 마을을 출발점으로 생각
		
		ArrayList<ArrayList<edge>> graph = new ArrayList();
		for(int i=0;i<=N;i++) {
			graph.add(new ArrayList<edge>());
		}
		
		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 value = Integer.parseInt(st.nextToken());
			graph.get(from).add(new edge(to, value));
		}
		
		//오고 가는데 드는 비용의 최댓값
		int[] allValue = new int[N+1];
		int[] root = new int[N+1];
		for(int i=1;i<=N;i++) {
			Arrays.fill(root, maxNum);
			dijkstra(graph, root, i);
			allValue[i] += root[X];
		}
		
		Arrays.fill(root, maxNum);
		dijkstra(graph, root, X);
		for(int i=1;i<=N;i++) {
			allValue[i] += root[i];
		}
		
		Arrays.sort(allValue);
		System.out.println(allValue[N]);
	}
	
	static void dijkstra(ArrayList<ArrayList<edge>> graph,int[] root, int start) {
		root[start]=0;
		PriorityQueue<edge> pq = new PriorityQueue<>();
		pq.add(new edge(start,0));
		
		while(!pq.isEmpty()) {
			edge now = pq.poll();
			if(root[now.to] < now.value)continue;
			
			for(int i=0;i<graph.get(now.to).size();i++) {
				edge next = graph.get(now.to).get(i);
				if(now.value+next.value < root[next.to]) {
					root[next.to] = now.value+next.value;
					pq.add(new edge(next.to,root[next.to]));
				}
			}
		}
	}
	static class edge implements Comparable<edge>{
    	int to;
    	int value;
    	edge(int to, int value){
    		this.to=to;
    		this.value=value;
    	}
		@Override
		public int compareTo(edge o) {
			return Integer.compare(this.value, o.value);
		}
    }
}