[백준/C++] 줄다리기 (No. 31444)

 

문제

문제 설명

 

 

풀이

 

[문제 풀이]

 

처음에 이 문제를 봤을 때 어떻게 풀어야할지 감이 잘 안왔다.

 

모든 경우를 전부 구하면 2^2000으로 시간이 초과됐고, 우선순위 큐를 이용해 그리디하게 풀어도 동점의 경우 명확하지 않다는 문제가 있었기 때문이다.

 

고민을 하다 힌트를 보니 이분탐색으로 문제를 풀 수 있겠다는 생각이 들었다.

 

먼저 두 팀의 팀워크 점수를 A값보다 크거나 같게 만들 수 있는지 검사한다.

그러면 같은 팀이 된 사람들의 점수가 A보다 크거나 같아야 하므로, i번째 사람과 j번째 사람의 팀워크 점수가 A보다 작다면 두 사람은 같은 팀이 되면 안된다는 뜻이다.

 

이제 같은 팀이 되면 안되는 사람들의 조합을 구했으면, 실제로 같은 팀이 되지 않도록 사람들의 팀을 나눈다.

 

이렇게 팀을 나누었을 때, 모순이 생기면 불가능 한 경우가 되는 것이다.

 

이렇게 점수를 기준으로 이분탐색을 하면 O(log(score)*N^2)으로 문제를 해결할 수 있게 된다.

 

 

 

[아이디어 정리]

1. 팀워크 수치의 최솟값이 최대값이 되는 점수를 찾기 위해 이분탐색으로 점수를 구한다.
2. 이분탐색으로 구한 현재 점수가 A라면 팀워크 점수가 A보다 작은 사람들은 같은 팀이 되면 안된다.
3. 같은 팀이 되면 안되는 사람들을 뽑아 다른 팀으로 배치한다. (이때, BFS나 DFS를 이용해 다른 팀이 되도록 구현)
4. 만약 서로 같은 팀이 되면 안되는 사람이 같은 팀에 있다면, 모순이 발생했으므로 A점수는 불가능한 경우다.
5. A 점수를 얻는게 가능한지 불가능한지 여부에 따라 다음에 탐색할 점수를 변경해 계산한다. 

 

 

Code

 

 

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

bool dfs(vector<int> &visited, vector<vector<int>>&nd, int num)
{
	if (visited[num]==2)
	{
		visited[num] = 0;
	}
	for (int i=0; i<nd[num].size(); i++)
	{
		int nNum = nd[num][i];
		if (visited[nNum]==2)
		{
			visited[nNum] = (visited[num] + 1) % 2;
			if (!dfs(visited, nd, nNum))
				return false;
		}
		else
		{
			if (visited[nNum]!= ((visited[num] + 1) % 2))
			{
				return false;
			}
		}
	}
	return true;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	int N;
	cin >> N;	
	vector<vector<int>>g(N, vector<int>(N));
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < N; j++)
		{
			cin >> g[i][j];
		}
	}
	int st = 1, ed = 1000000, mid;
	while(st<=ed)
	{
		mid = (st + ed) / 2;
		vector<vector<int>> nd(N);
		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (g[i][j]<mid)
				{
					nd[i].push_back(j);
					nd[j].push_back(i);
				}
			}
		}
		vector<int> visited(N, 2);
		bool flag = true;
		for (int i=0; i<N; i++)
		{
			if (visited[i]==2)
			{
				if (!dfs(visited, nd, i)) {
					flag = false;
					break;
				}
			}
		}
		if (!flag) {
			ed = mid - 1;
		}
		else
		{
			st = mid + 1;
		}
	}
	cout << ed << endl;

}

---

 

중간에 오류가 생겨서 왜 안풀리는지 한참 고민했다.

알고보니 배열의 값을 바꿔야 하는데, 다른 값을 바꿔서 생긴 오류였다.

 

한번에 풀이가 떠오르지 않으니 난이도에 비해 생각보다 오래 걸리는 문제였다...

 

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