dy = [1,-1,0,0]; dx = [0,0,1,-1]
def DFS(y,x):
if visited[y][x]:
return
visited[y][x] = 1
for y1,x1 in graph[y][x]:
if not match[y1][x1]:
match[y1][x1] = y,x
return 1
for y1,x1 in graph[y][x]:
if DFS(*match[y1][x1]):
match[y1][x1] = y,x
return 1
N,M = map(int,input().split())
graph = [[set() for x in range(M)] for y in range(N)]
for y in range(N):
for x in range(M):
if (y+x)%2:
continue
for i in range(4):
y1,x1 = y+dy[i],x+dx[i]
if N>y1>=0 and M>x1>=0:
graph[y][x].add((y1,x1))
for _ in range(int(input())):
a,b = map(lambda x:int(x)-1,input().split())
y1,x1,y2,x2 = a//M,a%M,b//M,b%M
graph[y1][x1].discard((y2,x2)); graph[y2][x2].discard((y1,x1))
match = [[0]*M for i in range(N)]
for y in range(N):
for x in range(M):
if (y+x)%2:
continue
visited = [[0]*M for i in range(N)]
DFS(y,x)
for y in range(N):
for x in range(M):
if (y+x)%2:
y1,x1 = match[y][x]
print(y*M+x+1,y1*M+x1+1)이분탐색 응용문제
이분탐색 문제라는 사실을 알고도 어떻게 적용시켜야할지 찾기 어려웠던 문제였다. 체스판에서 힌트를 얻을 수 있는 문제이다. 체스판은 검은색과 흰색으로 이루어져있다. 이때 2*1 도미노는 무조건 검은색 한개와 흰색 한개 위에 놓여지게 된다. 따라서 체스판의 검은색-흰색을 이분그래프로 놓고 이분탐색을 실행하여 문제를 해결할 수 있다.
풀이를 설명하면,
1. 체스판에서 검은색을 시작지점으로 두고 각 검은색 좌표에서 상,하,좌,우를 간선으로 하는 그래프를 만든다.
2. 입력으로 주어지는 값에 대한 그래프를 제거한다.
3. 이분탐색을 실행한다.
여담) 파이썬 기준 이 문제 성능 1위가 되었다.
