[JAVA] 백준 1238 - 파티

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

1238번: 파티

 

🤔 문제 접근

처음 떠올린 풀이 방법은 N개의 마을에서 파티가 열리는 X번 마을까지의 최소 거리를 구하고

X번 마을에서 각각의 N개의 마을까지의 최소 거리를 구해 더한 뒤, 최소 값들 중 최대 값을 구하는 것이었다.

A 마을에서 B마을까지의 최소 거리를 구하기 위해 최단 경로 탐색 알고리즘인 다익스트라 알고리즘을 사용했다.

 

하지만 위 풀이 방식으로 문제를 풀 경우 우선순위 큐를 사용한 다익스트라 알고리즘을 이용하더라도

N * (N+M)logN의 시간 복잡도를 갖게되어 최대 데이터 값으로 생각했을 때 1억을 초과하므로 

시간 초과가 우려되었다.

 

따라서 각각의 마을에서 X번째 마을까지의 거리 정보를 반대로 저장하여

1. 역으로 X번째 마을에서 각 마을까지의 최소 거리를 구하고

2. 원래 구하려고했었던 X번째 마을에서 각 마을까지의 최소 거리를 구해 

1번과정에서 구한 각각의 최소 거리값들과 2번과정에서 구한 최소 거리값들을 더해

최대 값을 구하고자 했다.

 

이 방법을 사용할 경우 1번과정에서 마을 수 만큼 반복하여 다익스트라 알고리즘을 수행하지 않아도 되어

실행 시간을 대폭 줄일 수 있었다. 

=> (1번과정) + (2번과정)  = 1 * (N + M)log N +  1* (N+M) log N = 2 * (N+M) logN

 

1번과정과 2번과정을 수행하는 코드가 중복된 내용이 많아서 

flag 변수를 이용했다.

🚨CODE

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


public class Main {
	static ArrayList<Node>[] road;
	static ArrayList<Node>[] reverse;
	static int[] dist;
	static int flag = 0;
	public static void main(String[] args) throws Exception  {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		int n = Integer.parseInt(st.nextToken()); // 학생수
		int m = Integer.parseInt(st.nextToken()); // 단방향 도로 수
		int x = Integer.parseInt(st.nextToken()); // 파티하는 마을
		
		road = new ArrayList[n+1];
		reverse = new ArrayList[n+1];
		int[] result = new int[n+1];
		
		for(int i = 1; i<=n; i++) {
			road[i] = new ArrayList<>();
			reverse[i] = new ArrayList<>();
		}
		
		for(int i = 0; i<m; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());

			road[a].add(new Node(b,v)); 
			reverse[b].add(new Node(a,v));
		}
		
		boolean[] visit = new boolean[n+1];
		dist = new int[n+1];
		
		for(int i = 1; i<=n; i++) {
			dist[i] = Integer.MAX_VALUE;
		}
		
		dist[x] = 0;
		check(x, visit);
		flag += 1;
		for(int i = 1; i<=n; i++) {
			result[i] = dist[i];
		}
		for(int i = 1; i<=n; i++) {
			dist[i] = Integer.MAX_VALUE;
		}
		dist[x] = 0;
		Arrays.fill(visit, false);
		check(x, visit);
		for(int i = 1; i<=n; i++) {
			result[i] += dist[i];
		}
		
		int answer = 0;
		for(int i = 1; i<=n; i++) {
			answer = Math.max(result[i], answer);
		}
		System.out.println(answer);
		
	}
	public static void check(int start, boolean[] visit) {
		PriorityQueue<Node> pq = new PriorityQueue<>();
		pq.add(new Node(start, 0));
		
		if(flag == 0) {
			while(!pq.isEmpty()) {
				Node curNode = pq.poll();
				if(visit[curNode.end])
					continue;
				
				visit[curNode.end] = true;
				
				for(Node node : reverse[curNode.end]) {
					if(dist[node.end] > dist[curNode.end] + node.value) {
						dist[node.end] = dist[curNode.end] + node.value;
						pq.add(new Node(node.end, dist[node.end]));
					}
				}
			}
		}
		else {
			while(!pq.isEmpty()) {
				Node curNode = pq.poll();
				if(visit[curNode.end])
					continue;
				
				visit[curNode.end] = true;
				
				for(Node node : road[curNode.end]) {
					if(dist[node.end] > dist[curNode.end] + node.value) {
						dist[node.end] = dist[curNode.end] + node.value;
						pq.add(new Node(node.end, dist[node.end]));
					}
				}
			}
		}
		
		
	}
}

class Node implements Comparable<Node>{
	int end;
	int value;
	
	Node(int end, int value) {
		this.end = end;
		this.value = value;
	}
	
	public int compareTo(Node n) {
		return value - n.value;
	}
}