[BOJ_10159 | Floyd]저울

풀이

저울 문제는 그래프 이론과 연관지으려고 한다면 플로이드 와샬 알고리즘을 이용해서 그리 어렵지 않게 해결할 수 있는 문제이다.

물건 1보다 2가 가벼운 경우, 즉 1 > 2 인 경우, 1에서 2로 가는 유향 그래프의 경로가 있다고 생각하면 된다.

이렇게 생각하면 물건 1과의 비교 결과를 알 수 없는 물건의 개수는 

플로이드 와샬 알고리즘을 이용하여 각각의 물건에 대해 경로가 없는 물건의 개수, 

즉 거리가 inifinite한 점들의 개수를 카운트 해주면 된다.

따라서 플로이드 와샬 알고리즘을 그대로 적용하되,

무방향 그래프가 아닌 유향 그래프임을 감안하여 해결해주어야 하며, 

또 한 가지 주의할 점은, 

1 > 2 라는 결과값이 주어졌을 때에는

물건 1에 대해 2도 비교할 수 있을 뿐더러

물건 2에 대해 1도 비교할 수 있음을 혼동하지 말아야 한다.

다시 말해서, 유향 그래프를 가정하고 플로이드 와샬 알고리즘을 수행한 후에는

반드시 경로값을 저장한 배열을 대각선 방향으로 대칭시켜야 한다는 것이다. 

소스 코드

import java.util.*;
public class BOJ_10159 {
    public static void main(String[] args){
        Scanner input = new Scanner(System.in);
        int n = input.nextInt();
        int[][] dis = new int[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dis[i][j] = 100;
            }
        }
        int m = input.nextInt();
        for(int i=0;i<m;i++){
            int i1 = input.nextInt()-1;
            int j1 = input.nextInt()-1;
            dis[i1][j1] = 1;
        }
 
        //floyd
        for(int k=0;k<n;k++){
            for(int i=0;i<n;i++){
                for(int j=0;j<n;j++){
                    if(dis[i][j] > dis[i][k]+dis[k][j])
                        dis[i][j] = dis[i][k]+dis[k][j];
                }
            }
        }
 
        //if 1 and 2 are connected, 2 and 1 are also connected
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(dis[i][j] != 100 && dis[j][i] == 100)
                    dis[j][i] = dis[i][j];
            }
        }
 
        for(int i=0;i<n;i++){
            int cnt = 0;
            for(int j=0;j<n;j++){
                if(dis[i][j] >= 100) cnt++;
            }System.out.println(cnt-1);
        }
    }
}