BOJ 9522 - 직선 게임

BOJ 9522 - 직선 게임

[ 분류 : 이분 매칭(Bipartite matching), Greedy, Game theory ]

  문제가 다소 독특하여 포스팅하고자 한다. 나는 증가경로를 이용하여 접근해봤다.

  문제를 보면 알겠지만, 한 점에 대해 x축 또는 y축에 그을 수 있으므로, 총 2개의 직선을 그을 수 있다. 그렇다면 처음에 게임을 시작하는 상근이는 시작할 점과 축을 정하고, 그 이후에 여기에 종속되어 번갈아 가며 이전 직선 위의 점을 선택해야 한다. 즉, 상근이는 점뿐만 아니라 축도 정할 수 있다. 축이 정해진 시점에서 x축과 y축이 번갈아가며 등장하는 구조가 될 수밖에 없다(1).

  또 x와 y에 대해 이분 그래프를 구성할 수 있다. x축에 평행하는 서로 다른 두 개의 직선은 절대로 겹칠 수 없고, 또 y축도 같은 논리로 독립적이기 때문에 x는 y와 또다시금 y는 x와 연결될 수 있기에 이분 그래프로 구성할 수 있다(2).

  (1)과 (2)에 의해서 이분 그래프에서 상근이가 정하는 방향대로 노드를 선택하는 것으로 증명할 수 있다. 이쯤오면 까먹을 수도 있다. 노드는 최대 2개의 축을 그을 수 있다. 따라서 상근이는 처음에 간선을 선택하는 게 아니라, 방향과 노드를 정하는 것이기 때문에, 선영이에게 연결된 간선들(edges)에서 선택하도록 하는 것이다(하나의 간선이 아니라, not a edge).

※ 왼쪽(파랑색)이 x, 오른쪽(주황색)이 y를 뜻합니다.

  게임이론으로 돌아오면 상근이는 그려진 선분의 개수가 짝수이어야 승리할 수 있으며(위에서 간, 반대로 선영이는 홀수이어야 승리할 수 있다.

  게임이 끝나고나면 선택된 간선은 증가경로로 표현할 수 있으며, 그 증가경로를 따라서 게임이 진행된다고 볼 수 있다. 그렇다면 상근이가 이기기 위해서는 노드와 방향이 선택된 시점에서 어느 노드를 선택하더라도 반드시 증강경로가 있어야 함을 알 수 있다.

  이론적으로 하나의 Component내의 매칭 결과가 K라면 거기에 사용되는 증가경로는 K+1가 된다. 따라서 증가경로는 2*K+1개로 홀수가 된다. forest라고 하더라도 귀납법으로 증명이 가능하다. 따라서 게임이론에 적용하면 주어진 그래프의 매칭이 완전 매칭인 경우 간선이 홀수이기 때문에 상근이가 어느 노드를 선택하든 질 수 밖에 없다.

  반대로 완전 매칭이 아닌 경우엔 시작 노드를 매칭에 포함되지 않는 노드를 선택하면 된다. 특정 노드 k에 대응하는 m노드가 있을 때, m은 매칭 결과에 포함된다. m이 매칭에 포함되지 않는다면 k와 m이 새로운 매칭이 되므로 전제가 모순이 된다. 즉, 매칭이 되지 않은 노드를 선택하면 그에 대응하는 노드가 또다른 노드와 연결되어 있기 때문에 선영이가 무슨 노드를 고르든 반드시 게임을 이어나갈 수 있기 때문이다. 따라서 이 경우 상근이는 매칭되지 않은 특정 노드 하나를 고르면 반드시 이긴다.

#include<cstdio>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
const int MAX_V = 500, INF = 1e9;
int level[MAX_V], A[MAX_V], B[MAX_V];
bool used[MAX_V];
queue<int> q;
vector<int> adj[MAX_V];
void bfs(int& n) {
	int i, u;
	for (i = 0; i < n; i++) {
		if (!used[i]) {
			level[i] = 0;
			q.push(i);
		}
		else level[i] = INF;
	}
	while (!q.empty()) {
		u = q.front(), q.pop();
		for (int& v : adj[u]) if (B[v] != -1 && level[B[v]] == INF) {
			level[B[v]] = level[u] + 1;
			q.push(B[v]);
		}
	}
}
int dfs(int u) {
	for (int& v : adj[u]) if (B[v] == -1 || level[B[v]] == level[u] + 1 && dfs(B[v])) {
		used[u] = 1;
		A[u] = v;
		B[v] = u;
		return 1;
	}
	return 0;
}
int main() {
	int N, x, y, f, matched = 0, i, can = 1, xcnt=0,ycnt=0;
	bool  x_axis[MAX_V] = {}, y_axis[MAX_V] = {};
	scanf("%d", &N);
	while (N--) {
		scanf("%d%d", &x, &y);
		x--, y--;
		adj[x].push_back(y);
		if (!x_axis[x]) {
			x_axis[x] = 1;
			xcnt++;
		}
		if (!y_axis[y]) {
			y_axis[y] = 1;
			ycnt++;
		}
	}
	can &= xcnt == ycnt;
	memset(A, -1, sizeof A);
	memset(B, -1, sizeof B);
	while (can) {
		bfs(N);
		f = 0;
		for (i = 0; i < MAX_V; i++) if (!used[i])
			f += dfs(i);
		if (!f) break;
		matched += f;
	}
	can &= xcnt == matched;
	puts(can ? "Slavko" : "Mirko");
	return 0;
}