백준 10159번 - 저울 (C++)

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

10159번: 저울

 

이전에 푼 키 순서 문제와 거의 같다.

 

이렇게 "순서"에 관련된 문제들은 위상정렬도 생각하게 된다. 위상정렬은 inorder와 outorder를 새면서 bfs돌며 순서를 정하는 방식이다.

 

아무튼, 이 문제에서 플로이드-워셜로 관계 찾는 기법을 복습해보았다.

 

초기화를 하고 dp를 사용해 각 정점이 경유하여 갔을 때 더 빠르게 갈 수있으면 갱신하는 것이 플로이드 워셜이다. 그러나 여기서는 말했듯이 그저 관계성만 보기 때문에 1, 0으로만 판단한다. 

 

그리고 이 둘이 관계성이 있는가를 판단하는 코드가

 

for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (dp[i][j] == 1 || dp[j][i] == 1) cnt++;
		}
	}

 

이 부분인데 여기서 dp[i][j], dp[j][i]를 모두 보는 이유는

 

i -> j가 가능하거나, j -> i 가 가능하면 관계성이 있는 것 이기 때문이다.

 

단방향이기 때문에 i - > j 가 가능하더라도 j - > i 는 불가능한 경우가 있기 때문이다.

 

물론 이 문제도 나보다 무거운 그래프, 가벼운 그래프로 구별하여 각각 순회해도 답을 구할 수 있다.

 

#include <iostream>

using namespace std;

int N, M;
int dp[101][101] = { 0, };

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);


	cin >> N >> M;

	for (int i = 0; i < M; i++) {
		int s, t;
		cin >> s >> t;

		dp[t][s] = 1;
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				if (dp[i][k] == 1 && dp[k][j] == 1) dp[i][j] = 1;
			}
		}
	}

	for (int i = 1; i <= N; i++) {
		int cnt = 0;
		for (int j = 1; j <= N; j++) {
			if (dp[i][j] == 1 || dp[j][i] == 1) cnt++;
		}

		cout << N - 1 - cnt << '\n';
	}
}