[백준] 10159. 저울

문제 링크

[백준] 10159. 저울

풀이 과정

우리는 입력 예시의 첫 번째와 두 번째 줄에 적힌 비교 결과를 통해 물건 1이 가장 무겁고, 그 다음 물건 2가 무겁고, 물건 3이 셋 중 가장 가볍다는 결론을 내릴 수 있습니다.

위 그림처럼, 물건을 정점으로 두고 무게 비교를 기준으로 방향 그래프를 그리면, 두 물건이 서로 무게 비교가 가능한 지 여부를 판단할 수 있습니다.

예를 들어, 물건 1과 4는 비교가 가능합니다. 물건 1은 2보다 무겁고, 물건 2는 3보다 무겁고, 물건 3은 4보다 무거우므로 물건 1 > 물건 2 > 물건 3 > 물건 4 라는 비교가 가능합니다.

하지만, 물건 1과 5는 비교가 불가능합니다. 위 그래프를 보면, 물건 1에서 4까지 이어지는 경로는 있지만, 4에서 5로 이어지는 경로가 없습니다. 마찬가지로, 물건 5에서 4로 이어지는 경로는 있지만, 4에서 1로의 경로가 없습니다.

위 예시를 통해 정점 x로부터 y까지, 혹은 정점 y로부터 x까지의 경로가 존재하게 되면, 두 물건 x와 y 사이의 비교가 가능하게 된다는 점을 알 수 있습니다.

모든 정점에서 모든 정점으로의 최단 거리를 구하는 플로이드-워셜 알고리즘을 사용해 2차원 배열을 만들면, 시작 정점에서 목적지 정점까지의 최단 거리 뿐만 아니라, 목적지 정점까지 갈 수 있느냐 없느냐를 판단할 수 있게 됩니다. 따라서, 위 특징을 이용하기 위해 플로이드-워셜 알고리즘을 사용하되, 이 문제에서는 원래 목적인 비용 갱신의 의미 보단, 갈 수 있냐 없냐에 초점을 둬 코드를 작성하면 됩니다.

코드

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int N = sc.nextInt();
        int M = sc.nextInt();
        boolean[][] map = new boolean[N][N];

        for (int i = 0; i < M; i++) {
            map[sc.nextInt() - 1][sc.nextInt() - 1] = true;
        }

        for (int k = 0; k < N; k++) {
            for (int i = 0; i < N; i++) {
                for (int j = 0; j < N; j++) {
                    if (map[i][k] && map[k][j]) map[i][j] = true;
                }
            }
        }

        for (int i = 0; i < N; i++) {
            int cnt = 0;

            for (int j = 0; j < N; j++) {
                if (i == j) continue;
                if (!map[i][j] && !map[j][i]) cnt++;
            }

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