[알고리즘] 백준 10159번: 저울 (C++)

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

10159번: 저울

 

개인적으로 (https://draw-code-boy.tistory.com/151) 이 문제와 똑같다고 느껴졌다.

저 문제를 풀지 않고, 이 문제를 시도했으면 어렵게 느껴졌을 거 같다.

플로이드 와샬로 나올 수 있는 문제 키워드 중 하나일 거 같다.

 

#include <iostream>
#include <cmath>
#define MAX 500 + 1
#define INF 987654321
using namespace std;

int graph[MAX][MAX];
int cache[MAX][MAX];
int n, m;

void floydWarshall() {
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cache[i][j] = graph[i][j];
		}
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (cache[i][k] != INF && cache[k][j] != INF) {
					cache[i][j] = min(cache[i][j], cache[i][k] + cache[k][j]);
				}
			}
		}
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j) cache[i][j] = 0;
		}
	}
}

int main() {
	cin >> n >> m;

	// init
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			graph[i][j] = INF;
		}
	}

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;
		graph[a][b] = 1;
	}

	floydWarshall();

	for (int i = 1; i <= n; i++) {
		int cnt = 0;

		// i로부터 갈 수 있는 노드가 몇 개인가
		for (int j = 1; j <= n; j++) {
			if (cache[i][j] == INF || cache[i][j] == 0) continue;
			else cnt++;
		}

		// 도착 노드가 i가 되는 경우는 몇 개인가
		for (int j = 1; j <= n; j++) {
			if (cache[j][i] == INF || cache[i][j] == 0) continue;
			else cnt++;
		}

		cout << (n - 1) - cnt << '\n';
	}

	return 0;
}