[파이썬] 백준 11280 : 2-SAT - 3 (플레4)

[파이썬] 백준 11280 : 2-SAT - 3 (플레4)

• https://www.acmicpc.net/problem/11280

---

풀이

방향성 생각

• 2 SAT 기본 문제
• 입력이 들어오면 음수 노드를 양수로 만들어서 매핑해준다.
• 풀고 알았는데, 보통 짝수를 참, 홀수를 거짓으로 매핑해서 각 node 0을 새로운 new node 0,1로 매핑한다.
• 명제가 들어오면 전처리 이후, 대우 명제와 함께 그래프에 넣어주기.
• 한 SCC 내에 x와 ~x가 같이 존재하면 모순이므로 명제를 참으로 만들 수 없다.

 

---

전체코드

import sys
sys.setrecursionlimit(10**6)
input = lambda : sys.stdin.readline().strip()

# 입력
N,M = map(int,input().split())

cvt = lambda x : 2*abs(int(x)) - (int(x)<0) 
neg_node = lambda x : x+1 if x%2 else x-1

G = [[] for _ in range(2*N+1)]
for _ in range(M):
    a,b = map(cvt,input().split())
    G[neg_node(a)].append(b)
    G[neg_node(b)].append(a)

# 타잔
V = [-1]*(2*N+1)
P = [-1]*(2*N+1)
counter = [0]
on_stack = [False]*(2*N+1)
stack = []

SCC = []
def dfs(x):

    V[x] = counter[0]
    P[x] = counter[0]
    on_stack[x] = True
    stack.append(x)
    counter[0] += 1

    for nx in G[x]:
        if V[nx] == -1:
            dfs(nx)
            P[x] = min(P[x],P[nx])
        elif on_stack[nx]:
            P[x] = min(P[x],V[nx])

    if V[x] == P[x]:
        scc = []
        while True:
            xx = stack.pop()
            on_stack[xx] = False
            scc.append(xx)
            if x == xx:
                break
        SCC.append(scc)

# SCC 만들기
for x in range(1,2*N+1):
    if V[x] == -1:
        dfs(x)

# 그룹 번호 붙이기
group = [0]*(2*N+1)
for idx,scc in enumerate(SCC):
    for x in scc:
        group[x] = idx

# 각 x와 ~x 모순 발생하면 탈출
possible = 1
for i in range(1,N+1):
    pos = 2*i
    neg = pos -1
    if group[pos] == group[neg]:
        possible =0
        break
print(possible)

코멘트

• .