[Floyd] BOJ 10159 저울

문제 링크 : www.acmicpc.net/problem/10159

10159번: 저울

 

플로이드-와샬 문제라는 것을 캐치하는 것이 문제 해결의 80%는 되는 것 같은 문제이다.

각 물건들의 무게 관계를 그래프의 형태로 이해하고,

문제에서 요구하는 것이 그래프의 각 노드에서 도달할 수 없는 노드들의 갯수이므로

모든 노드에서 다른 모든 노드로의 최단거리를 구하는 플로이드-와샬 알고리즘이 적절함을 캐치해야 한다.

플로이드-와샬 알고리즘(Floyd-Warshall Algorithm)

그래프의 모든 가중치를 1로 둔 후, 한 노드에서 다른 노드로 도달할 수 있는 최단거리가 존재한다면 무게 관계가 존재하는 것이다.

 

하지만, 물건들의 무게 관계를 단순히 그래프로 나타내면 문제가 발생한다.

가령, 물건 A가 물건 B보다 무거울 때 B -> A의 간선을 생성하여 그래프를 만들어 보자.

생성한 그래프에서 우리는 B보다 무게가 작으면 반드시 A보다 무게가 작다는 사실을 알 수 있으므로, C -> B라는 간선이 존재할 때 우리는 A, C의 무게 관계에 대해서도 알 수 있다.

하지만 플로이드-와샬 알고리즘을 적용한다면 A -> C의 간선은 그래프에 존재하지 않으므로, A 입장에서는 C를 도달 불가능한 노드로 간주하게 된다.

따라서 그래프를 두 개 만들어 문제를 해결한다.

가벼운, 무거운 관계에 대한 그래프 두 개에 대해, 각자 플로이드-와샬 알고리즘을 적용한 뒤

두 그래프 모두에게서 도달할 수 없는 노드가 있다면, 그 노드가 무게관계를 알 수 없는 노드이다.

즉, 두 dist 배열의 값이 모두 INF라면, 도달할 수 없는 노드이다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
 
#define INF 99999999
 
using namespace std;
typedef pair<int, int> p;
 
int n, m, dist[101][101], dist2[101][101];
 
void floyd() {
    for (int middle = 1; middle <= n; middle++) {
        for (int from = 1; from <= n; from++) {
            for (int to = 1; to <= n; to++) {
                dist[from][to] = min(dist[from][to], dist[from][middle] + dist[middle][to]);
                dist2[from][to] = min(dist2[from][to], dist2[from][middle] + dist2[middle][to]);
            }
        }
    }
}
 
void init() {
    int f, s;
    cin >> n >> m;
 
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++) {
            if (i == j) {
                dist[i][j] = 0;
                dist2[i][j] = 0;
            }
            else {
                dist[i][j] = INF;
                dist2[i][j] = INF;
            }
        }
 
    for (int i = 0; i < m; i++) {
        cin >> f >> s;
        dist2[f][s] = 1;
        dist[s][f] = 1;
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    floyd();
 
    int cnt = 0;
    for (int i = 1; i <= n; i++) {
        cnt = 0;
        for (int j = 1; j <= n; j++) {
            if (i == j) continue;
            if (dist[i][j] == INF && dist2[i][j] == INF) cnt++;
        }
        printf("%d\n", cnt);
    }
 
    return 0;
}