[BOJ] 1238 파티 JAVA

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

1238번: 파티

 

메모리 : 24,396kb
실행시간 : 2,756ms

 

문제분석

다익스트라

단방향 그래프에서 인접행렬을 사용해
다익스트라로 최단경로를 구하자 !!!

 

걸린시간

40분 ⏱️

 

풀이방법

1. 인접 행렬 생성
2. 최단 거리 저장 배열 생성
3. 각 집마다 최단거리 계산 (다익스트라)
4. 계산된 거리를 이용해 가장 거리가 먼 집 구하기

 

포인트

다익스트라 알고리즘만 구현할 수 있다면 쉽게 풀 수 있는 문제 ! ! !
근데 최적화는 실패했다 .. 뭔가 겨우 통과한 느낌
다른 사람 풀이 궁금궁금

 

코드

package study.day1013;

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

public class BOJ_1238_파티 {	// 메모리 : 24,396 kb		실행시간 : 2,756 ms
	static int N, M, X, ans = Integer.MIN_VALUE;
	static int[][] map;
	static int[][] len;
	static boolean[] visited;
	public static void main(String[] args) throws Exception {
		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());
			map[Integer.parseInt(st.nextToken())][Integer.parseInt(st.nextToken())] = Integer.parseInt(st.nextToken());
		}

		len = new int[N + 1][N + 1];	// 최단거리 저장 배열
		for (int i = 0; i <= N; i++) {
			Arrays.fill(len[i], Integer.MAX_VALUE);	// 최대값으로 초기화 
		}
		int minW, minV;
		for (int i = 1; i <= N; i++) {
			len[i][i] = 0;	// 시작정점
			visited = new boolean[N + 1];
			for (int n = 1; n <= N; n++) {
				minW = Integer.MAX_VALUE; 
				minV = -1;
				for (int j = 1; j <= N; j++) {
					if(!visited[j] && minW > len[i][j]) {
						minW = len[i][j];
						minV = j;
					}
				}
				if(minV == -1) continue;
				visited[minV] = true;

				for (int j = 1; j <= N; j++) {
					if(!visited[j] && map[minV][j] != 0 && len[i][j] > len[i][minV] + map[minV][j]) {
						len[i][j] = len[i][minV] + map[minV][j];
					}
				}
			}
		}
		for (int i = 1; i <= N; i++) {
			if(i == X) continue;
			ans = Math.max(ans, len[i][X] + len[X][i]);
		}
		System.out.println(ans);
	}
}