[백준] 10159번 : 저울

10159번: 저울

---

[Floyd Warshall (플로이드 와샬)]

일반적인 플로이드 와샬 알고리즘으로 모든 정점에서 다른 모든 정점으로의 최단 거리를 구한다. 이 때 가볍고 무겁다는 것은 양방향이 아닌 단방향이다.

 

그러므로 a정점에서 b정점에 대하여 어느 것이 가볍고 무거운지 모르고, 마찬가지로 b정점에서 a정점에 대하여 어느 것이 가볍고 무거운지 모른다면 (distance[a][b] == INF && distance[b][a] == INF) 비교 결과를 알 수 없는 것이다.

 

플로이드 와샬 알고리즘을 사용했으므로 시간 복잡도는 O(n^3)이 될 것 이다.

# Code </>

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

public class Main {

    static final int INF = 1000000000;
    static int[][] d = new int[101][101];

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int n = Integer.parseInt(br.readLine());
        int m = Integer.parseInt(br.readLine());

        for(int i=1; i<=n; i++)
            for(int j=1; j<=n; j++)
                d[i][j] = (i != j) ? INF : 0;

        for(int i=0; i<m; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int heavy = Integer.parseInt(st.nextToken());
            int light = Integer.parseInt(st.nextToken());

            d[heavy][light] = 1;
        }

        for(int k=1; k<=n; k++)
            for(int i=1; i<=n; i++)
                for(int j=1; j<=n; j++)
                    d[i][j] = Math.min(d[i][j], d[i][k] + d[k][j]);

        for(int i=1; i<=n; i++) {
            int cnt = 0;
            for (int j = 1; j <= n; j++)
                if(d[i][j] == INF && d[j][i] == INF)
                    cnt++;

            System.out.println(cnt);
        }
    }
}