[C++] 백준 10159 : 저울

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

10159번: 저울

백준 10159번 저울을 풀었다.

 

예제 1번의 입력을 넣었을 때 dist 배열이다.

dist	1	2	3	4	5	6
1	0	1	2	3	INF	INF
2	INF	0	1	2	INF	INF
3	INF	INF	0	1	INF	INF
4	INF	INF	INF	0	INF	INF
5	INF	INF	INF	1	0	INF
6	INF	INF	INF	2	1	0

 

dist[i][j] INF가 아니면 i 노드와 j 노드가 비교가 가능한 것이고, INF라면 비교가 불가능 한 것이다.

 

1번 노드부터 마지막 노드까지 반복문을 돌려서 비교 결과를 알 수 없는 물건의 개수를 구한다.

예를 들어 4번 노드의 경우 4번 노드만 보면 본인을 제외한 값이 모두 INF인데, dist[temp][4]를 확인해보면 모든 노드가 4번 노드와 비교할 수 있다. 이 경우엔 0이 출력된다.

 

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
#include <algorithm>
#include <vector>
#pragma warning(disable:4996)
using namespace std;

#define INF 10000000

int adj[101][101];
int dist[101][101];

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

	int start, end;
	for (int i = 1; i <= m; i++) {
		scanf("%d %d", &start, &end);
		adj[start][end] = 1;
	}

	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			if (i == j)
				dist[i][j] = 0;
			else if (adj[i][j] != 0)
				dist[i][j] = adj[i][j];
			else
				dist[i][j] = INF;
		}
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++)
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
		}
	}

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

		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == INF)
				v.push_back(j);
		}

		while (!v.empty()) {
			int temp = v.back();
			v.pop_back();
			if (dist[temp][i]==INF) { // If temp node and i node can not compare
				cnt++;
			}
		}

		cout << cnt << '\n';
	}


	return 0;
}