[백준 11281번] 2-SAT - 4 (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 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):
  a,b = map(int,input().split())
  graph[-a].append(b)
  graph[-b].append(a)
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(1); print(*visited[1:N+1])
else:
  print(0)

2-SAT 기본문제이다.

SCC + 위상정렬로 해결할 수 있다.

2-SAT - 3 [백준 11280번] 2-SAT - 3 (Python3) (tistory.com) 에서 True를 만드는 방법까지 출력한다.

2-SAT - 3을 풀었으니 쉽게 해결할 수 있을 것이라고 생각했는데, 생각보다 난관이 많은 문제였다.

 

풀이를 설명하면,

1. 2-SAT - 3 방식대로 scc를 구한다. (각 scc에 속한 원소들도 저장한다)

2. check 함수가 0이면 0을 출력한다.

3. check 함수가 1인 경우, 늦게 만들어진 scc 순서대로 해당 scc에 속한 원소들을 false로 두고, 그 거짓은 True로 두면서 dfs를 실행한다.

4. 원소들의 true false 여부를 출력한다.

 

3에서 늦게 만들어진 순서대로 하는 이유는 위상정렬에 있다. 타잔 알고리즘으로 scc를 생성하면, scc의 순서는 곧 위상정렬의 역순이 되기 때문이다. (자세한 설명은 https://m.blog.naver.com/kks227/220803009418 이곳을 참고)

 

 

2-SAT 알고리즘과, 타잔 알고리즘의 위상정렬에 대해서 알 수 있게된 좋은 문제였다.

 

 

오늘의 교훈) 2-SAT 활용문제를 풀어보자