[백준 10159] 저울 (C++)

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

10159번: 저울

1. 주의할 점

- 플로이드-와샬 알고리즘을 사용한다

 

2. 구현

- 각각의 비교 결과를 담는 Arr[][] 배열을 사용한다

- 입력받는 2개의 물건에 대해 앞쪽이 더 크므로 Arr[a][b] = 1, Arr[b][a] = -1로 선언하여 둘의 대소관계를 정리한다

- 플로이드 와샬 알고리즘을 통해 비교하려는 2개의 값이 모두 0이 아닌 같은 값을 지닐 경우, 해당 값으로 배열을 초기화한다

- 플로이드 와샬 알고리즘이 끝난 이후, i 물건이 j 물건과 비교가 가능할 때(Arr[][]값이 0이 아닐 때) 비교할 수 없는 개수를 구해서 출력한다

 

#include <iostream>
#include <algorithm>
using namespace std;
int arr[101][101];

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int num, query, a, b;
	cin >> num >> query;
	for (int i = 0; i < query; i++) {
		cin >> a >> b;
		arr[a][b] = 1;
		arr[b][a] = -1;
	}
	for (int k = 1; k <= num; k++) 
		for (int i = 1; i <= num; i++) 
			for (int j = 1; j <= num; j++) 
				if (arr[i][k] == arr[k][j] && arr[i][k] != 0)
					arr[i][j] = arr[i][k];

	for (int i = 1; i <= num; i++) {
		int cnt = num-1;
		for (int j = 1; j <= num; j++) 
			if (arr[i][j] != 0) cnt--;		
		cout << cnt << '\n';
	}			
	return 0;
}