[백준 16367번] TV Show Game (Python3)

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**4)

def DFS(now):
  global id,s
  visited[now] = nowid = id
  stack.append(now)
  for next in graph[now]:
    if sccnum[next]:
      continue
    if not visited[next]:
      id += 1
      DFS(next)
    visited[now] = min(visited[now],visited[next])
  if visited[now]==nowid:
    s = len(scc); scc.append([])
    while stack:
      x = stack.pop()
      sccnum[x] = s; scc[-1].append(x)
      if x==now:
        break
        
def check():
  for i in range(1,N+1):
    if sccnum[i]==sccnum[-i]:
      return
  return 1

def dfs(now):
  visited[now] = 1; visited[-now] = 0
  for next in graph[now]:
    if visited[next]==-1:
      dfs(next)

N,M = map(int,input().split())
graph = [[] for i in range(2*N+1)]
for _ in range(M):
  q = [*map(lambda x:1 if x=="R" else -1 if x=="B" else int(x),input().split())]
  for i in range(3):
    for j in [1,2]:
      j = (i+j)%3
      graph[-q[i*2]*q[i*2+1]].append(q[j*2]*q[j*2+1])
visited = [0]*(2*N+1); scc = [[]]; sccnum = [0]*(2*N+1); stack = []
for i in range(1,N+1):
  if not visited[i]:
    id = 1
    DFS(i)
if check():
  visited = [-1]*(2*N+1); scc.reverse()
  for s in scc:
    for i in s:
      if visited[i]==-1:
        visited[i] = 0; dfs(-i)
  print(*map(lambda x:"R" if x==1 else "B",visited[1:N+1]),sep="")
else:
  print(-1)

2-SAT 응용문제

2-SAT 문제라는 사실을 알고 문제를 풀어서 그런지 쉽게 해결할 수 있었다.

 

핵심은 2~3명이 맞춰야 한다는 것이다. 원래 2-SAT 문제를 풀 때 (X V Y) 가 있으면 X가 부정일 때 Y가 무조건 참이라는 사실을 이용해서 그래프를 만들었었다. 이와같이, 이 문제에서 3개의 전등 X,Y,Z가 있다고 가정하면, X를 맞추지 못했을 경우 Y와 Z가 무조건 참이어야 한다. Y가 거짓일때도 X,Z가 무조건 참이어야 하고 Z도 마찬가지이다.

따라서 이를 그래프로 나타내줄 수 있고, 그래프로 나타내기만 하면 풀이 방식은 2-SAT - 4 [백준 11281번] 2-SAT - 4 (Python3) (tistory.com) 문제와 완전히 똑같다.

 

2-SAT라는 사실을 알고 풀어서 쉽게 해결했지만 만약 몰랐다면 전등이 3개라는 사실에 속아서 2-SAT라는 사실을 떠올리기 힘들었을 수도 있었겠다는 생각이 드는 문제였다. 

 

 

오늘의 교훈) 다양한 2-SAT 문제를 해결하자