[백준 10159] 저울(Java)

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

이 문제는 플로이드 워셜 알고리즘을 이용하여 풀 수 있습니다. 각 물건에 대한 비교 결과를 알 수 없는 물건의 개수를 출력하는 문제이기 때문에 모든 노드에서의 최단 경로 배열을 구하는 플로이드 워셜 알고리즘을 사용합니다. 여기서 주의할 점은 Boolean 타입의 작은 순서의 dp 배열과 큰 순서의 dp 배열 2개를 생성하는 것입니다. 각 dp 배열을 플로이드 워셜 알고리즘으로 true로 채운 후 두 dp 배열을 OR 연산을 하게 되면 자기보다 크거나 작은 모든 경로를 얻을 수 있습니다. 따라서 dp 배열을 탐색하면서 false인 경우 비교 결과를 알수 없는 물건이므로 카운트합니다.

다음은 코드입니다.

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

class Main{
    static int N,M;
    static boolean[][] dp, reverseDp;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        M = Integer.parseInt(br.readLine());

        dp = new boolean[N+1][N+1];
        reverseDp = new boolean[N+1][N+1];

        for(int i=0;i<M;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            dp[a][b] = true;
            reverseDp[b][a] = true;
        }

        for(int k=1;k<=N;k++){
            for(int i=1;i<=N;i++){
                for(int j=1;j<=N;j++){
                    if(dp[i][k] && dp[k][j]) dp[i][j] = true;
                    if(reverseDp[i][k] && reverseDp[k][j]) reverseDp[i][j] = true;
                }
            }
        }

        for(int i=1;i<=N;i++){
            for(int j=1;j<=N;j++){
                dp[i][j] |= reverseDp[i][j];
            }
        }

        StringBuilder sb = new StringBuilder();
        for(int i=1;i<=N;i++){
            int cnt = 0;
            for(int j=1;j<=N;j++){
                if(i==j) continue;

                if(!dp[i][j]) cnt++;
            }
            sb.append(cnt).append("\n");
        }
        System.out.println(sb);

    }
}