[백준 1507] 궁금한 민호 (Java)

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

1507번: 궁금한 민호

1. 주의할 점

- 최단경로에 사용되는 간선인지 아닌지 구분이 필요하다

- 최단경로 알고리즘에 대해 알고 있어야 한다

 

2. 구현

- 모든 그래프의 경로를 알기 위해 Arr[][] 배열을 생성과 초기화한다

- 최단경로가 저장된 값을 Result[][] 배열에 저장한다

- Result[][] 배열에 입력된 간선들에 대한 정보를(중복 제외) 우선순위큐에 저장한다(가중치의 오름차순으로 정렬)

- 우선순위큐에서 간선들을 1개씩 빼면서, 해당 간선과 Arr[][] 값을 비교하면서 이미 최단경로라면 Continue를 수행하고 아니라면 Arr[][]갱신과 Answer에 해당 간선의 가중치를 더한다. 이후, 플로이드 와샬 알고리즘이 구현되어 있는 Floyd() 함수를 수행한다

- 우선순위 큐 내의 모든 간선들을 확인한 후,  Arr[][]와 Result[][]를 비교하여 틀린 값이 1개라도 있으면 Answer를 -1로 바꾼 후 비교를 종료한다

- 모든 비교가 끝난후엔 Answer값을 출력한다

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

class Main {
    public static class Info implements Comparable<Info> {
        int from,to,val;       
        public Info(int from, int to, int val){
            this.from = from;
            this.to = to;
            this.val = val;
        }       
        @Override
        public int compareTo(Info o){
            return Integer.compare(this.val,o.val);
        }
    }
    
    static final int maxi = 10000*401;
    static int node,answer;
    static int arr[][],result[][];
    static PriorityQueue<Info> pq;
    
    static void floyd(){
        for(int k=1;k<=node;k++)
            for(int i=1;i<=node;i++)
                for(int j=1;j<=node;j++)
                    if(arr[i][j]>arr[i][k]+arr[k][j])
                        arr[i][j]=arr[i][k]+arr[k][j];
    }
    
	public static void main (String[] args) throws java.lang.Exception {
	    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	    String str = br.readLine().trim();
	    StringTokenizer st = new StringTokenizer(str);
	    node = Integer.parseInt(st.nextToken());
	    
	    //초기화
	    answer=0;
	    arr = new int[node+1][node+1];
	    result = new int[node+1][node+1];
	    pq = new PriorityQueue<>();
	    Info ii;
	    for(int i=1;i<=node;i++){
	        for(int j=1;j<=node;j++){
	            if(i==j) arr[i][j]=0;
	            else arr[i][j]=maxi;
	        }
	    }
	    
	    for(int i=1;i<=node;i++){
	        str = br.readLine();
	        st = new StringTokenizer(str);
	        for(int j=1;j<=node;j++){
	            int val = Integer.parseInt(st.nextToken());
	            result[i][j] = val;
	            if(j>i){
	                pq.offer(new Info(i,j,val));
	            }
	        }
	    }
	    
	    while(!pq.isEmpty()){
	        ii = pq.poll();
	        int cf = ii.from;
	        int ct = ii.to;
	        int cv = ii.val;
	        if(arr[cf][ct]<=cv) continue;
	        arr[cf][ct]=cv;
	        arr[ct][cf]=cv;
	        floyd();
	        answer+=cv;
	    }
	    
	    for(int i=1;i<=node;i++){
	        for(int j=1;j<=node;j++)
	            if(arr[i][j]!=result[i][j]){
	                answer=-1;
	                break;
	            }
	        if(answer==-1) break;
	    }
	    System.out.println(answer);
	}
}