[BOJ/백준 10159/C++] 저울

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

10159번: 저울

 

[문제 요약]

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

- 예를 들어, 총 6개의 물건이 있고, 다음 5개의 비교 결과가 주어졌다고 가정하자.

• [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는 모든 다른 물건과의 비교 결과를 알 수 있다. 

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

 

[문제 조건]

- 첫 줄에는 물건의 개수 N ( 5 ≤ N ≤ 100 )이 주어지고, 둘째 줄에는 미리 측정된 물건 쌍의 개수 M ( 0 ≤ M ≤ 2,000 )이 주어진다.

- 다음 M개의 줄에 미리 측정된 비교 결과가 한 줄에 하나씩 주어진다.

- 각 줄에는 측정된 물건 번호를 나타내는 두 개의 정수가 공백을 사이에 두고 주어지며, 앞의 물건이 뒤의 물건보다 더 무겁다.

- 시간 제한 : 1초

- 메모리 제한 : 256MB

 

[문제 풀이]

이 문제는 크게 2가지 방법으로 문제를 풀 수 있다. ( 플로이드 와샬 or BFS이용 )

 

일단 문제를 어떻게 접근할지 생각해보자. 주어지는 입력에서 각 물건별로 대소비교 결과를 알려준다. 필자는 이 정보를 방향성 그래프로 한번 나타내보았다.

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

위 그림은 1이 2보다 크고 2가 3보다 크다라는 의미로 방향성 그래프로 나타내었다.

 

여기서 각 번호별로 BFS를 이용하여 탐색을 진행하면 본인보다 작은 물건들을 알아낼 수 있다. 하지만 한번만 탐색을 진행하면 자신보다 큰 물건에 대한 정보를 얻을 수 없다.

 

따라서 반대 방향으로 BFS를 한번 더 진행하면 그 물건에 대해 비교결과를 알 수 있는 물건들의 개수가 나온다.

 

근데 필자는 반대방향으로 BFS를 수행하지 않고 자신보다 작은 물건들을 탐색할때 , 배열을 따로 하나 만들어 탐색하는 동안 만난 물건에 대한 값을 하나씩 증가시켰다.

 

말로 표현하기 좀 어려워서 그림으로 한번 나타내보았다.

 

먼저 1번부터 BFS를 돌려서 탐색한 번호들은 아래 그림과 같을 것이다.

이때 배열에다가 탐색하면서 확인한 번호에 해당하는 칸에 1씩 증가시켜준다. 1번칸에는 탐색하면서 확인한 번호 + 1을 저장해준다. 이것이 의미하는건 비교결과를 알 수 있는 물건의 개수인 것이다.

 

위 과정을 2번에도 적용시키면

위 그림과 같은 값들이 저장될 것이다. 2번칸에는 원래 있던 값 1과 탐색하면서 만난 번호의 갯수 2개, 그리고  +1을 해서 4가 된 것이다.

 

위 과정들을 모든 번호에 대해 수행하면 아래와 같이 결과가 나온다.

 

이때 이 배열이 의미하는 값은 비교 결과를 알 수 있는 물건들의 개수이기 때문에 각 값들을 최대 갯수에서 빼서 출력하면 정답이 된다.

 

[소스 코드1]

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <string>

using namespace std;

int N, M;
vector<vector<int>> dt;
vector<int> ans;

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

	cin >> N >> M;
	dt.resize(N + 1);
	ans.resize(N + 1);
	int s, e;
	for (int i = 0; i < M; i++)
	{
		cin >> s >> e;
		dt[s].push_back(e);
	}
	for (int i = 1; i <= N; i++)
	{
		queue<int> q;
		q.push(i);
		int cnt = 1;
		vector<bool> ck(N + 1);
		ck[i] = true;
		while (!q.empty())
		{
			int tmp = q.front(); q.pop();
			for (int k = 0; k < dt[tmp].size(); k++)
			{
				if (ck[dt[tmp][k]]) continue;
				ans[dt[tmp][k]]++;
				cnt++;
				q.push(dt[tmp][k]);
				ck[dt[tmp][k]] = true;
			}
		}
		ans[i] += cnt;
	}
	for (int j = 1; j <= N; j++)
	{
		cout << N - ans[j] << "\n";
	}
}

 

 

위 방법말고 플로이드 와샬로도 문제해결이 가능하다.

 

아이디어로는 플로이드와샬 방법을 통해 만든 배열이 의미하는게 i번 노드에서 j번 노드로 가는 최단거리를 의미하는데, 만약 값이 INF로 되어 있으면 i번 부터 j번으로 갈 수 없다는것을 의미한다.

 

이 문제를 그래프로 나타냈을때 특정 노드에서 특정 노드로 갈 수 있는 방법이 존재하기만 한다면 대소비교가 가능하다는 것을 의미함으로 플로이드 와샬 방법을 적용시킨 후 i에서j로가나 j에서i로가나 둘 중 하나라도 경로가 존재한다면 비교가 가능하다는 것을 의미함으로 경로가 둘 다 없는 경우를 count해서 출력하면 답이 될 것이다.

[소스 코드2]

 

#include <iostream>
#include <vector>
#include <stdio.h>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <string>

using namespace std;

int N, M;
vector<vector<bool>> dt;
vector<int> ans;

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

	cin >> N >> M;
	dt.resize(N + 1);
	for (int i = 1; i <= N; i++) dt[i].resize(N + 1);
	int s, e;
	for (int i = 0; i < M; i++)
	{
		cin >> s >> e;
		dt[s][e] = true;
	}

	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if (dt[i][k] && dt[k][j]) dt[i][j] = true;
			}
		}
	}

	for (int i = 1; i <= N; i++)
	{
		int cnt = 0;
		for (int j = 1; j <= N; j++)
		{
			if (dt[i][j] || dt[j][i]) cnt++;	
		}
		cout << N -  cnt - 1 << "\n";
	}
}

마지막에 1을 뺀 경우는 i==j 경우를 제외하기 위함이다.

 

 

굳