백준 1238번) 파티 (JAVA)

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

1238번: 파티

 

#문제

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

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

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

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

 

#알고리즘

그래프 이론

다익스트라

 

#난이도

Gold 3

#풀이방법

알고리즘은 다익스트라라고 되어있지만 생각해보면

플로이드 와샬 알고리즘을 통해 각자의 모든 노드의 최단거리를 구해 1번부터 N번까지 각자 모든 노드의 최단거리를 구한후 

 

int max = 0;
        
        for(int i=1; i<N+1; i++) {
            
            if(i == X)
                continue;
            
            max = Math.max(max,node[i][X]+node[X][i]);
            
        }

Math.max를 통해 1번부터 N번까지(X를 제외) 

반복문을 이용하여 i -> X + X ->i의 최댓값을 구한다.

 

알고리즘에 다익스트라라고 제시되어 있지만, 곰곰히 생각해보면 문제를 풀 수 있는 더 편한 알고리즘이 있다면 자신만의 풀이방법으로 문제를 해결하는 것이 더 좋다고 본다.

 

#전체 코드

import java.util.*;
 
public class Main {
    
    static final int INF = 10000001;
    
    public static void main(String[] args) {
        
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();//학생
        
        int[][] node = new int[N+1][N+1];
        
        for(int i=1; i<N+1; i++) {
            for(int j=1; j<N+1;j++) {
                
                if(i == j)
                    continue;//자신의 노드는 제외
                
                node[i][j] = INF;
            }
        }
        
        int M = sc.nextInt();//단방향 도로
        
        int X = sc.nextInt();//파티를 여는 장소
        
        for(int i=0; i<M; i++) {
            
            int m1 = sc.nextInt();
            int m2 = sc.nextInt();
            int d = sc.nextInt();
            
            node[m1][m2] = d;//단방향 도로
        }
        
        for(int k=1; k<N+1; k++) {
            
            for(int i=1; i<N+1; i++) {
                
                for(int j=1; j<N+1; j++) {
                    
                    node[i][j] = Math.min(node[i][j],node[i][k]+node[k][j]);
                                
                }
                
            }
            
        }//폴로이드 와샬 알고리즘 이용 - > 모든 노드의 최단거리 구하기
        
        int max = 0;
        
        for(int i=1; i<N+1; i++) {
            
            if(i == X)
                continue;
            
            max = Math.max(max,node[i][X]+node[X][i]);
            
        }//X를 제외한 i->X + X->i의 maximum을 구함
        
        System.out.println(max);
        
 
    }
 
}