파티 [JAVA] (백준 1238)

 

문제

문제 링크 : https://www.acmicpc.net/problem/1238

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1초	128MB	17717	8311	5462	45.283%

문제

N개의 숫자로 구분된 각각의 마을에 한 명의 학생이 살고 있다.

어느 날 이 N명의 학생이 X (1 ≤ X ≤ N)번 마을에 모여서 파티를 벌이기로 했다. 이 마을 사이에는 총 M개의 단방향 도로들이 있고 i번째 길을 지나는데 Ti(1 ≤ Ti ≤ 100)의 시간을 소비한다.

각각의 학생들은 파티에 참석하기 위해 걸어가서 다시 그들의 마을로 돌아와야 한다. 하지만 이 학생들은 워낙 게을러서 최단 시간에 오고 가기를 원한다.

이 도로들은 단방향이기 때문에 아마 그들이 오고 가는 길이 다를지도 모른다. N명의 학생들 중 오고 가는데 가장 많은 시간을 소비하는 학생은 누구일지 구하여라.

입력

첫째 줄에 N(1 ≤ N ≤ 1,000), M(1 ≤ M ≤ 10,000), X가 공백으로 구분되어 입력된다. 두 번째 줄부터 M+1번째 줄까지 i번째 도로의 시작점, 끝점, 그리고 이 도로를 지나는데 필요한 소요시간 Ti가 들어온다. 시작점과 끝점이 같은 도로는 없으며, 시작점과 한 도시 A에서 다른 도시 B로 가는 도로의 개수는 최대 1개이다.

모든 학생들은 집에서 X에 갈수 있고, X에서 집으로 돌아올 수 있는 데이터만 입력으로 주어진다.

출력

첫 번째 줄에 N명의 학생들 중 오고 가는데 가장 오래 걸리는 학생의 소요시간을 출력한다.

 

풀이

경로를 탐색하는 문제인데, 왕복하기 때문에 두가지 경우를 더해야 한다.

모든 점에서 x로 가는 거리 + x에서 모든 점으로 가는 거리

N이 1000이기 때문에, 플로이드-와샬을 사용하여

모든 점에서 다른 점으로 가는 거리 (Link State)를 만들어놓는다면 쉽게 구할거라 생각했다.

반면 다익스트라로 푼다면, 모든 점에 대해 탐색을 해줘야 한다.

우선순위 큐를 사용하지 않는다면, 다익스트라 알고리즘의 시간 복잡도가 $O(V^2 + E)$에 V번이므로 시간복잡도가 더 높지만,

우선순위 큐를 사용한다면 $O(ElogV)$에 V번으로 시간복잡도가 더 작게 된다.

따라서 간선(E)가 큰 경우 다익스트라를  사용하는게 좋고

정점(V)가 간선보다 적은 경우 플로이드 와샬이나 벨만 포드를 사용하는게 좋을 것 같다

 

코드

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


public class Main {
	
	static int N;
	static int X;
	static int M;
	static int map[][];
	
	public static void main(String[] args) throws IOException{
		StringTokenizer st;
		BufferedReader br = new java.io.BufferedReader(new InputStreamReader(System.in));
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		X = Integer.parseInt(st.nextToken())-1;
		
		map = new int[N][N];
		
		for(int i=0; i<N; i++) {
			for(int j=0; j<N; j++) {
				map[i][j] = 20000000;
			}
			map[i][i] = 0;
		}

		
		
		int start;
		int end;
		for(int i=0; i<M; i++){
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			map[start-1][end-1] = Integer.parseInt(st.nextToken());
		}
		
		//x에서 각각의 점으로 가는 시간 + 각각의 점에서 x로 오는 시간
		floyd(N, map);
		int answer = 0;
		for(int i=0; i<N; i++) {
			answer = Math.max(answer, map[i][X] + map[X][i]);
		}
		System.out.println(answer);
		
	}
	public static void floyd(int n, int[][] dist) {
		for(int k=0; k<n; k++) {
			for(int i=0; i<n; i++) {
				if(i==k) continue;
				for(int j=0; j<n; j++) {
                    if(dist[i][k] >= 20000000) continue;
					if(j==k || i==j) continue;
					dist[i][j] = Math.min(dist[i][k] + dist[k][j], dist[i][j]);
				}
			}
		}
	}
}

 

결과

근데 사실 1초가 넘었는데, 어떻게 통과했는지 모르겠다.

 

전문가가 아니라 정확하지 않은 지식이 담겨있을 수 있습니다.
언제든지 댓글로 의견을 남겨주세요!