[백준 2519번] 막대기 (Python)

import sys
sys.setrecursionlimit(10**4)
input = lambda : [*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):
  return ccw(x1,y1,x2,y2,x3,y3)*ccw(x1,y1,x2,y2,x4,y4)<0 and ccw(x3,y3,x4,y4,x1,y1)*ccw(x3,y3,x4,y4,x2,y2)<0

def DFS(now):
  global id
  ID[now] = nowid = id
  stack.append(now)
  for next in graph[now]:
    if scc[next]:
      continue
    if not ID[next]:
      id += 1
      DFS(next)
    ID[now] = min(ID[now],ID[next])
  if ID[now]==nowid:
    SCC.append([])
    while 1:
      x = stack.pop()
      scc[x] = len(SCC); SCC[-1].append(x)
      if x==now:
        return

def dfs(now):
  visited[now] = 1; visited[(now+3*N)%(6*N)] = -1
  for next in graph[now]:
    if not visited[next]:
      dfs(next)

[N] = input()
stick = [input() for i in range(3*N)]
graph = [[] for i in range(6*N)]
for i in range(N):
  for j in [0,1,2]:
    for k in [1,2]:
      graph[i*3+j+3*N].append(i*3+(j+k)%3)
for i in range(3*N):
  for j in range(i+1,3*N):
    if crossed(*stick[i],*stick[j]):
      graph[i].append(j+3*N); graph[j].append(i+3*N)

stack = []; scc = [0]*6*N; SCC = []
ID = [0]*6*N
for i in range(3*N):
  if not ID[i]:
    id = 1
    DFS(i)
if sum(scc[i]==scc[i+3*N] for i in range(3*N)):
  print(-1)
else:
  SCC.reverse(); visited = [0]*6*N
  for S in SCC:
    for i in S:
      if not visited[i]:
        dfs((i+3*N)%(6*N))
  print(sum(visited[i]<0 for i in range(3*N)))
  for i in range(3*N):
    if visited[i]<0:
      print(i+1,end=" ")

2-SAT 응용문제

TV Show Game [백준 16367번] TV Show Game (Python3) (tistory.com) 을 약간 업그레이드 시킨 문제이다.

 

풀이를 설명하면,

1. 막대기를 남기는 경우를 True, 남기지 않는 경우를 False로 둔다.

2. 각 학생의 세 개의 막대가 있을 때, 2개 이상이 참이어야 한다. 예를들어 막대를 x,y,z로 두면 x가 거짓이면 y와 z가 참이어야 한다. 이를 간선으로 나타낸다. ( = TV Show Game)

3. 선분교차 ( = [백준 17386번] 선분 교차 1 (Python3) (tistory.com) ) 한 막대가 있는 경우 두 막대 중 한 막대만이 참이어야 한다. 예를들어 막대 x,y가 교차하고 있으면 x가 참이면 y가 거짓이어야 한다. 이를 간선으로 나타낸다.

4. 이외 풀이 방식은 2-SAT 알고리즘을 이용한다. ( = [백준 11281번] 2-SAT - 4 (Python3) (tistory.com) )

 

아이디어가 비슷하기에 2-sat라는 사실을 알고 TV Show Game 문제를 풀고나면 쉽게 해결할 수 있는 문제이다. 하지만 2-sat라는 사실을 모른 채로 풀면 꽤나 애먹었을 것 같다.

 

 

오늘의 교훈) 2-sat로 해결할 수 있는지 잘 관찰하자