[백준/BOJ] 백준 10159번 : 저울

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

10159번: 저울

 

a가 b보다 무거울 때 b에서 a로 가는 그래프로 생각하고 'info[b][a] = a가 b보다 무겁다는 정보가 있을 때 1'에 정보를 표시했다. 그리고 info를 플로이드 와샬을 이용해 특정 위치에서 도달할 수 있는 위치를 판단하여 비교가 가능한지 확인하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n, m;
int info[105][105]; //[b][a] : a가 b보다 무겁다는 정보가 있을때 1
vector<int> result;

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

	cin >> n;
	cin >> m;

	for (int i = 0; i < m; i++) {
		int a, b;
		cin >> a >> b;

		info[b][a] = 1;
	}

	//a가 b보다 무거울때 b->a의 그래프로 생각하고 플로이드 와샬 알고리즘을 통해 비교 가능한 그래프 만들기

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {

				info[i][j] = max(info[i][j], (info[i][k] & info[k][j]));

			}
		}
	}

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

			if (i == j) {
				continue;
			}

			//i에서j 또는 j에서i까지 도달할 수 있는지 확인
			//즉 i와 j의 비교가 가능할 때
			if (info[i][j] == 1 || info[j][i] == 1) {
				continue;
			}

			else {
				this_result++;
			}
		}
		result.push_back(this_result);
	}

	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << "\n";
	}

	return 0;
}