[백준 14750번] Jerry and Tom (Python3)

import sys
def input(): return [*map(int,sys.stdin.readline().split())]

def ccw(x1,y1,x2,y2,x,y):
  return (x2-x1)*(y-y1)-(y2-y1)*(x-x1)

def crossed(x1,y1,x2,y2,x3,y3,x4,y4):
  ccw12,ccw34 = ccw(x1,y1,x2,y2,x3,y3)*ccw(x1,y1,x2,y2,x4,y4),ccw(x3,y3,x4,y4,x1,y1)*ccw(x3,y3,x4,y4,x2,y2)
  if ccw12==0 and ccw34==0:
    if min(x1,x2)<=max(x3,x4) and min(x3,x4)<=max(x1,x2) and min(y1,y2)<=max(y3,y4) and min(y3,y4)<=max(y1,y2):
      return 1
    return 1
  elif ccw12<=0 and ccw34<=0:
    return 1

def check(i,j):
  for n in range(N):
    if ccw(*hole[i],*point[n],*point[(n+1)%N])!=0 and crossed(*hole[i],*mouse[j],*point[n],*point[(n+1)%N]):
      return
  return 1

def DFS(i):
  if visited[i]:
    return
  visited[i] = 1
  for j in graph[i]:
    if match[j]<0:
      match[j] = i
      return 1
  for j in graph[i]:
    if DFS(match[j]):
      match[j] = i
      return 1

N,K,H,M = input()
point,hole,mouse = [[input() for i in range(n)] for n in [N,H,M]]
graph = [[] for i in range(H)]
for i in range(H):
  for j in range(M):
    if check(i,j):
      graph[i].append(j)
match = [-1]*M
for k in range(K):
  for i in range(H):
    visited = [0]*H
    DFS(i)
print("Possible" if not match.count(-1) else "Impossible")

선분교차 + 이분매칭으로 해결하였다.

 

풀이를 설명하면,

1. 구멍과 쥐 간에 간선을 잇는 이분그래프를 만든다. 이때 간선이 존재하는 조건은 구멍-쥐를 잇는 선분과 구멍이 존재하는 선분을 제외한 나머지 모든 선분간에 선분교차가 없는것이다. (선분교차가 있으면 벽이 시야를 가린다는 뜻이다)

2. 1에서 만든 이분그래프를 각 구멍에서 K번 이분매칭을 실행하여 최대매칭하였을 때, 모든 쥐가 매칭이 되었는지를 출력한다.

 

문제를 읽자마자 풀이방법은 바로 파악할 수 있었다. 그러나 선분교차 과정에서 실수가 정말 많이 나왔다.

선분교차에서 한 점에서 만나는 경우도 선분교차로 취급 (https://rapun7el.tistory.com/51) 해야하고, 구멍이 선분에 포함된 경우를 제외해야한다는 점이 까다로웠다.

 

 

오늘의 교훈) 선분교차 판별에서 실수하지말자