BOJ #10159 - 저울

https://icpc.me/10159

# 문제 분류
최단 경로 찾기 (Floyd-Warshall Algorithm)

풀이 접근 방법 :

 

1. 각각 물건의 대소관계를 directed graph로 생각한다면 최단 경로 알고리즘으로 해결할 수 있다는 것을 알 수 있다.

2. 따라서 마찬가지로 모든 쌍들에 대한 거리를 찾기 위해 Floyd-Warshall을 이용하여 값을 갱신한다.

3. 각 노드들에 대한 다른 노드들과의 거리를 탐색하며 dist[i][j], dist[j][i] 모두 INF가 나오면 알 수 없는 것, 카운팅.

---

역사@1613에서의 사건의 선후관계와 본 문제의 대소관계가 똑같이 적용되는 것을 알 수 있다.

역사@1613을 풀었다면 그대로 이 문제도 풀 수 있을 것이다. :)

 

#include <iostream>
#include <algorithm>
 
using namespace std;
 
int INF = 1e9;
int N, M, a, b, arr[110][110];
 
int main(){
    for(int i=0; i<110; i++){
        for(int j=0; j<110; j++){
            arr[i][j] = INF;
            arr[j][j] = 0;
        }
    }
 
    scanf("%d %d", &N, &M);
    for(int i=0; i<M; i++){
        scanf("%d %d", &a, &b);
        arr[a][b] = 1;
    }
 
    for(int i=1; i<=N; i++){
        for(int j=1; j<=N; j++){
            for(int k=1; k<=N; k++){
                arr[j][k] = min(arr[j][k], arr[j][i] + arr[i][k]);
            }
        }
    }
 
    for(int i=1; i<=N; i++){
        int cnt = 0;
        for(int j=1; j<=N; j++){
            if(arr[i][j] != INF || arr[j][i] != INF);
            else cnt++;
        }
        printf("%d\n", cnt);
    }
 
    return 0;
}