[백준 10159] 저울

문제출처: https://www.acmicpc.net/problem/10159

풀이

대충 그래프 문제이니, 예제를 그래프로그려봅니다. 그리고 보기의 답을 보면, x와 비교할 수없는 물건의 갯수는 x에서 다른 노드로 가는길과 다른 노드에서 x로 가는 길이 없을 때만 해당합니다. 결국, 플로이드와샬로 해결됨을 알 수 있습니다. 

부끄러운 얘기지만, 플로이드 코드를 작성해놓고 카운팅을하는 반복문작성에 시간을 많이 잡아먹었습니다. 헷갈리더라구요. 

플로이드알고리즘이 코드도 직관적이고 이해도 쉬운만큼, 그냥 눈으로만 보고 넘어갈 때가 있었는데 이번에 많이 반성했습니다. 

배운 개념은 꼭 복습을 하는 습관을 가집시다..

코드

#include<iostream>
using namespace std;
int map[101][101];
int main()
{
	int n, m, a, b;
	cin >> n >> m;
	for (int i = 0; i < m; i++)
	{
		cin >> a >> b;
		map[a][b] = 1;
	}
	//플로이드 돌려준다.
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (map[i][k] && map[k][j])map[i][j] = 1;
			}
		}
	}
	for (int i = 1; i <= n; i++) {
		int cnt = 0;
		for (int j = 1; j <= n; j++) {
			if (i == j)continue;
			//i에서 j로 가는길도없고, j에서 i로 가는길도 없을때 ++
			if (map[i][j] == 0 && map[j][i] == 0)cnt++;
		}
		cout << cnt << endl;
	}
}

결과