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

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

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

---

풀이

방향성 생각

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

 

---

전체코드

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)

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


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)

if possible:
    temp = [-1]*(2*N+1)
    for scc in reversed(SCC):
        for node in scc:
            if node%2:
                pos,neg = node+1,node
            else:
                pos,neg = node-1,node

            # x, ~x를 처음 발견 -> 현재 발견한 node를 False로, 나머지를 true로
            if all(temp[x] for x in [pos,neg]):
                temp[node] = False

    # x, ~x중 x만 골라내기
    answer = []
    for i in range(1,2*N+1,2):
        answer.append(1 if temp[i] != -1 else 0)
    print(*answer)

코멘트

• XOR로 x와 ~x를 빠르게 구해주기.