[BOJ-10159] 저울(JAVA)

백준 10159 두 배열의 합

 

10159번: 저울

 

문제 설명

 

 - 무게가 서로 다른 N개의 물건이 있다.

 

 - 각 물건은 1부터 N까지 번호가 매겨져 있다.

 

 - 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지 측정한 결과표를 가지고 있다.

 

 - 비교 결과에는 모순된 입력이 없다고 가정한다.

 

 - 물건의 개수 N과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 

   비교 결과를 알 수 없는 물건의 개수를 출력하라.

 

 - N개의 결과를 출력해야 하고, i번째 줄에는 물건 i와 비교 결과를 알 수 없는 물건의 개수를 출력하라.

 

---

 

입력 값

 

 - 첫 줄에는 물건의 개수 N이 주어진다.(5 <= N <= 100)

 

 - 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다.(0 <= M <= 2,000)

 

 - 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다.

 

 - 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며,

   앞의 물건이 뒤의 물건보다 더 무겁다.

 

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 해당 물건의 개수와 연관된 물건이 아닌 것의 개수를 구하면 된다.

 

 - 즉, 주어진 결과표를 바탕으로 몇 개의 물건이 연결되어 있는지 판단하면 된다.

 

 - 주어진 예제를 바탕으로 그래프를 만들 수 있다.

 

 - 가벼운 물건에서 무거운 물건으로 이동한다고 가정하면,

   예제 1에서는 1->2 / 2->3 / 3->4 / 5->4 / 6->5 의 형태를 가진다.

 

 - 여기서 1번과 연관된 물건들을 살펴보자.

   1->2->3->4 형태로 1번은 2, 3, 4와 연결되어 있고 5, 6은 연결되어 있지 않다.

 

 - 즉, 1번은 자기자신을 포함하여 4개의 물건과 연결되어 있다.

 

 - 4번과 연결된 물건들을 살펴보자.

   1->2->3->4에 의해서 1, 2, 3이 연결되어 있고, 6->5->4  형태로 5, 6이 연결되어 있다.

 

 - 즉, 4번은 자기자신을 포함하여 6개의 물건과 연결되어 있다.

 

 - 여기서 알 수 있는 것은 i번째 물건이 어떤 물건들과 연결되어 있는지 판단하는 방법은 간단하다.

   j -> i 이거나 i -> j 라면 물건 i는 물건 j와 연결되어 있다고 판단할 수 있다.

 

 - 결국, n개의 모든 경로에서 각 노드로 갈 수 있는지를 판단하면 된다.

 

 - 여기서 노드의 개수가 100개이기 때문에, 모든 노드가 연결되어 있는지 판단하기 위해서 플로이드-와샬을 이용하면 된다.

   시간복잡도는 O($N^3$) = O($100^3$) = 100만

최단 경로 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

 

 - 주어진 결과표 가중치를 1로 두고, 최단 경로를 판단하여 경로가 존재하면 물건이 연결되어 있다고 판단하면 된다.

 

---

 

 

소스 코드

 

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

// https://www.acmicpc.net/problem/10159
// 저울
public class Main {

    public static int boards[][] = new int[102][102];

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

        int N = Integer.parseInt(bf.readLine());

        int M = Integer.parseInt(bf.readLine());

        // 초기화
        for(int i=0;i<102;i++){
            for(int j=0;j<102;j++){
                boards[i][j] = 99999999;
            }
        }

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

            int s = Integer.parseInt(st.nextToken());

            int e = Integer.parseInt(st.nextToken());

            boards[s][e]=1;

        }
        
        // 플로이드-와샬
        for(int k=1;k<=N;k++){
            for(int i=1;i<=N;i++){
                for(int j=1;j<=N;j++){
                    boards[i][j] = Integer.min(boards[i][k] + boards[k][j],boards[i][j]);
                }
            }
        }

        for(int i=1;i<=N;i++){
            // 자기 자신
            int result = 1;

            for(int j=1;j<=N;j++){
                if(i==j){
                    continue;
                }
                // j -> i 로 갈 수 있는지
                result += boards[j][i] < 99999999 ? 1 : 0 ;
                // i -> j 로 갈 수 있는지
                result += boards[i][j] < 99999999 ? 1 : 0 ;
            }
            
            System.out.println(N - result);
        }
    }

}