백준 #10159 저울


BOJ #10159 - 저울

https://www.acmicpc.net/problem/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;
}