[백준 11280번] 2-SAT - 3 (Python3)

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

def DFS(now):
  global id,s
  visited[now] = nowid = id
  stack.append(now)
  for next in graph[now]:
    if scc[next]:
      continue
    if not visited[next]:
      id += 1
      DFS(next)
    visited[now] = min(visited[now],visited[next])
  if visited[now]==nowid:
    s += 1
    while stack:
      x = stack.pop()
      scc[x] = s
      if x==now:
        break

def check():
  for i in range(1,N+1):
    if scc[i]==scc[-i]:
      return 0
  return 1

N,M = map(int,input().split())
graph = [[] for i in range(2*N+1)]
for _ in range(M):
  a,b = map(int,input().split())
  graph[-a].append(b)
  graph[-b].append(a)
visited = [0]*(2*N+1); scc = [0]*(2*N+1); stack = []; s = 0
for i in range(1,N+1):
  if not visited[i]:
    id = 1
    DFS(i)
print(check())

2-SAT 기본문제이다.

SCC로 해결할 수 있다.

 

풀이를 설명하면,

1. a,b가 입력으로 주어질 때, -a가 참이면 (즉 a가 거짓이면) b가 무조건 참이어야 한다. 마찬가지로 -b가 참이면 a가 무조건 참이어야 한다. 이를 그래프로 표현한다.

2. 그래프의 간선을 따라 타잔알고리즘으로 scc를 찾는다.

3. 같은 scc 안에 어떤 값 x에 대해 x가 참일때와 거짓일 때(+x와 -x)가 동시에 포함되어 있으면 0을 출력하고 그렇지 않으면 1을 출력한다. (x가 참이면서 동시에 거짓일 수 없으므로)

 

SAT 문제가 무엇인지와 어떻게 해결하는지를 배울 수 있는 좋은 문제였다.

 

 

오늘의 교훈) SAT를 활용한 문제들도 풀어보자