[10159번][C/C++] 저울

https://www.acmicpc.net/problem/10159

10159번: 저울

 

N개의 물건이 주어지고 그 물건들에 대한 대소관계가 M개 주어질 때 각 물건들끼리 대소 관계를 파악할 수 있는지 없는지를 파악하는 문제이다.

 

이 문제에서 주목해야 할 포인트는 두가지 정도이다.

1. 저울의 대소관계는 방향성 그래프의 간선으로 생각할 수 있다.

예를 들어 A < B이고 B < C라면 A -> B, B -> C로의 단방향 간선 두 개로 생각할 수 있다.

2. 구해야하는 정보가 각 물건들로부터 각 다른 모든 물건들까지의 도달 가능 여부라는 것이다.

이는 모든 노드에서 다른 모든 노드로의 도달여부를 구하라는 문제로 해석할 수 있다.

모든 노드에서 다른 모든 노드로의 도달여부를 구하라고 한다면 플로이드 워셜 알고리즘이 직관적으로 바로 떠오르게 된다.

마침 노드가 최대 100개인 것을 보면 플로이드 워셜을 사용하는 방법을 유도한 문제라고 생각할 수 있다.

(일반적으로 플로이드 워셜은 노드가 500개 이하인 경우 사용 가능하다.)

 

즉 해결 방법은 다음과 같다.

1. dist[][] 배열을 INF로 초기화한다. (도달 불가능한 경우 플로이드 워셜을 수행한 뒤에도 INF가 바뀌지 않는다.)

2. 방향성 그래프로 입력을 받는다. (기본적으로 dist[][] 배열에 저장할 수 있다.)

3. 플로이드 워셜 알고리즘을 수행한다.

4. 플로이드 워셜 결과를 보며 각 i번 물건에서 다른 j번 물건까지 살펴보며 dist[i][j] 와 dist[j][i] 둘 다 INF라면 카운팅 한다.

5. 각 물건에 대해 카운팅한 값을 출력한다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>

#define INF 987654321

using namespace std;

int N, M;
int dist[101][101];

int main() {
    scanf("%d\n%d", &N, &M);

    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            dist[i][j] = INF;
        }
    }

    for (int i = 0; i < M; i++) {
        int a, b;
        scanf("%d %d", &a, &b);
        dist[a][b] = 1;
    }

    for (int k = 1; k <= N; k++) {
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= N; j++) {
                if (dist[i][k] != INF && dist[k][j] != INF && dist[i][j] > dist[i][k] + dist[k][j])
                    dist[i][j] = dist[i][k] + dist[k][j];
            }
        }
    }

    for (int i = 1; i <= N; i++) {
        int cnt = 0;
        for (int j = 1; j <= N; j++) {
            if (i == j) continue;
            if (dist[i][j] == INF && dist[j][i] == INF) cnt++;
        }
        printf("%d\n", cnt);
    }

    return 0;
}