본문 바로가기

카테고리 없음

[백준 1824번] 도미노 (Python3)

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위가 되었다.