[BOJ] 1733번: 등번호

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

이 문제의 풀이는 2가지가 있습니다.

1. bipartite matching

각 선수에 대해 가능한 두 등번호를 연결해두면 bipartite matching 문제로 변형할 수 있습니다. Hopcroft는 시간복잡도가 $O(V^{0.5}E)$이기 때문에 잘 구현되어있는 구현체를 사용하면 시간 제한 내에 충분히 들어올 수 있습니다. 

2. Graph Theory

등번호가 (3, 3) 이라던가, 혹은 (3, 3)이 있어서 3은 이미 쓸 수 없게 되었는데 다음에 등번호가 (3, 5)라던가 하는 이유로 등번호가 바로 고정되는 사람들을 미리 빼두고 생각합시다.

나머지들에 대해 등번호가 a, b인 사람이 있다고 할 때 노드 a와 b를 연결하는 간선을 생각해봅시다. 그러면 그렇게 만들어진 그래프에서 각 노드에 대해 양 쪽의 노드 중 하나를 매칭시켜줘야 하는 문제로 생각할 수 있습니다. 그리고 잘 생각해보면 Connected Component에서 E >= V-1인데 E > V가 되는 순간 무조건 불가능할거니 그래프의 각 Connected Component는 결국 E = V 혹은 E = V - 1의 꼴이 될 수 밖에 없습니다. 여기까지 이해하셨다면 구현 방향은 크게 어렵지 않게 잡힐 것 같습니다.

2번 방법의 시간복잡도는 $O(N + 1000000)$인게 분명한데 제 구현에 문제가 있었는지 수행 시간이 Hopcroft보다 2번이 더 오래걸리네요. 아무튼 재채점으로 인해 터져서 새로 풀었는데 굉장히 재밌었고 능지가 상승하는 기분이 들었습니다. 맞은 후에 다른 사람의 코드를 보니 재채점 이후에도 Hopcroft로 생존한 경우를 여럿 볼 수 있었습니다.

https://github.com/blisstoner/BOJ/blob/master/1733.cpp