백준 1132: 합

저울 성공

 

 

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

256 MB

6372

3963

3212

64.602%

문제

무게가 서로 다른 N 개의 물건이 있다. 각 물건은 1부터 N 까지 번호가 매겨져 있다. 우리는 일부 물건 쌍에 대해서 양팔 저울로 어떤 것이 무거운 것인지를 측정한 결과표를 가지고 있다. 이 결과표로부터 직접 측정하지 않은 물건 쌍의 비교 결과를 알아낼 수도 있고 알아내지 못할 수도 있다. 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자. ([1]은 1번 물건의 무게를 의미한다.)

[1]>[2], [2]>[3], [3]>[4], [5]>[4], [6]>[5]

우리는 [2]>[3], [3]>[4]로부터 [2]>[4]라는 것을 알 수 있다. 하지만, 물건 2와 물건 6을 비교하는 경우, 앞서의 결과만으로는 어느 것이 무거운지 알 수 없다. 이와 같이, 물건 2는 물건 1, 3, 4와의 비교 결과는 알 수 있지만, 물건 5, 6과의 비교 결과는 알 수 없다. 물건 4는 모든 다른 물건과의 비교 결과를 알 수 있다. 

비교 결과가 모순되는 입력은 없다고 가정한다. 위 예제의 기존 측정 결과에 [3]>[1]이 추가되었다고 가정하자. 이 경우 [1]>[2], [2]>[3]이므로 우리는 [1]>[3]이라는 것을 예측할 수 있는데, 이는 기존에 측정된 결과 [3]>[1]과 서로 모순이므로 이러한 입력은 가능하지 않다. 

물건의 개수 N 과 일부 물건 쌍의 비교 결과가 주어졌을 때, 각 물건에 대해서 그 물건과의 비교 결과를 알 수 없는 물건의 개수를 출력하는 프로그램을 작성하시오. 

입력

첫 줄에는 물건의 개수 N 이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M이 주어진다. 단, 5 ≤ N ≤ 100 이고, 0 ≤ M ≤ 2,000이다. 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다. 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.

출력

여러분은 N개의 줄에 결과를 출력해야 한다. i 번째 줄에는 물건 i 와 비교 결과를 알 수 없는 물건의 개수를 출력한다.

예제 입력 1 복사

6
5
1 2
2 3
3 4
5 4
6 5

예제 출력 1 복사

2
2
2
0
3
3

예제 입력 2 복사

9
11
2 1
3 1
2 8
2 9
7 8
4 5
6 7
6 3
1 7
6 2
1 9

예제 출력 2 복사

2
3
3
7
7
2
3
3
4

출처

이 문제는 처음에는 위상정렬인지 알고 위상정렬로 풀다가 실패해서 플로이드 워셜로 풀었다.

플로이드 워셜은 각 노드에서 노드별로 최단 거리를 다이나믹프로그래밍을 이용해서 계속 갱신해주는 알고리즘인데 , 잘 생각해보면 최단거리를 갱신한다는 것 자체가 일단 연결성을 확인한다는 것이다. 그럼 코드부터 보면

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
#define INF 987654321
using namespace std;
int n, m;//물건의 개수, 저울에 올라간 쌍의 갯수
bool dist[101][101];

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin >> n >> m;
	int heavy, right;
	for (int i = 1; i <= m; i++) {
		cin >> heavy >> right;// 더 무거운거
		dist[right][heavy] = true;
	} 
	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if (dist[i][k] == true && dist[k][j] == true) {//거쳐서 갈 수 있으면 
					dist[i][j] = true;
				}
			}
		}
	}
	//for (int i = 1; i <= n; i++) {
	//	for (int j = 1; j <= n; j++) {
	//		cout << dist[i][j] << ' ';
	//	}cout << endl;
	//}//연결이 가능한 그래프를 만들어서 출력한다.
	vector<int> result;
	for (int i = 1; i <= n; i++) {
		int answer = 0;
		for (int j = 1; j <= n; j++) {
			if (dist[i][j] == 1 || dist[j][i] == 1)answer++;
		}
		result.push_back(n - answer-1);
	}
	for (int i = 0; i < result.size(); i++) {
		cout << result[i] << '\n';
	}

	return 0;
}

이런 식으로 코드를 구성할 수 있는데 우선 연결간선을 쫙 연결해주고 

위의 주석처리된 부분을 실행시키면

6
5
1 2
2 3
3 4
5 4
6 5

이 예제를 넣으면

  1 2 3 4 5 6

1 0 0 0 0 0 0
2 1 0 0 0 0 0
3 1 1 0 0 0 0
4 1 1 1 0 1 1
5 0 0 0 0 0 1
6 0 0 0 0 0 0

이런 형태로 1~6까지 정점을 중간다리로 설정하고 갱신시킨 연결정보가 나온다.

1에서 2,3,4로 무게를 비교할 수 있고

2에서 1,3,4로 무게를 비교하고

3에서 1,2,4로 무게를 비교하고 

4는 전체가 다 가능하며

5는 6과

6은 5와 무게를 비교할 수 있다. 

비교방식은

1부터 살펴보면 1행 모든 열을 비교하고 1열에서 모든 행을 비교한다.

2는  2행과 연결된 모든 열을 비교하고 2열과 연결된 모든 행을 비교한다.

이 방식으로 연결된 다른 물건들의 갯수를 비교한다.

답은

연결되지 못하는 노드의 개수를 구하는 건데

노드가 6개이고  1은 3개의 노드와 연결되어있고 자기자신은 연결할 필요가 없음으로 2개를 제외하면 다 연결이 된다.