백준 11280번, 11281번: 2-SAT - 3, 4 (Strongly Connected Components)

 

문제링크:11280번: 2-SAT - 3 (acmicpc.net), 11281번: 2-SAT - 4 (acmicpc.net)

11281번: 2-SAT - 4

이 문제는 2-CNF식을 True로 만들기 위한 xi값들이 가능 한지, 그리고 가능 하다면 xi값들을 정하는 문제이다. 2-CNF식이란 &를 and, |를 or이라고 했을 때 식의 구조가 (x1|x2)&(x4|x3)&(xi|xj) 이렇게 임의의 xi들이 괄호 안에서는 or, 괄호 밖으로는 and로 묶였을 때의 식이다. 위 식을 True로 만들기 위해서는 모든 괄호 중 하나는 반드시 True여야 한다.

 

입력으로는 x1,x2..xi에서 i의 개수와 총 괄호식의 개수가 주어지고, 괄호식의 개수 만큼 정수 2개 i,j가 주어지는데 만약 양수라면 (xi | xj), 음수라면 (not xi | not xj) 형태로 생각하면 된다.

 

처음 이 문제를 접했을 때 어떻게 풀어야 하나 싶었다. 처음에 만약 가능한 경우를 간선들로 만들어 DFS로 따라가면 답이 나올 수 있지 않을까 해서 i, j 라면 (xi)->(xj), (xi)->(-xj), (-xi)->(xj) 이렇게 간선들을 만들어 DFS로 탐색을 해보았지만 역방향 간선까지 포함하면 한 조건 당 간선이 6개나 생겨 너무 많아졌고, 딱히 의미있는 그래프를 얻을 수도 없었다.

 

인터넷을 찾아본 결과 가능한 경우 중 (False)->(True) 형태의 경우를 간선으로 만든 뒤, SCC를 사용하면 문제를 찾을 수 있다고 한다. 왜 가능한 경우 6가지 중 하필 (F)->(T) 일까 생각해 보았는데, 만약 시작이 (T)이라면 뒤의 경우는 (T,F)에 상관 없이 (xi | xj) 을 만족 할 수 있다. 반면에 시작이 (F)이라면 뒤의 경우가 무조건 (T)여야 (xi | xj) 를 만족할 수 있기 때문에, 이후의 모순을 찾기 위해서는 확실한 xi와 xj의 관계를 알려주는 간선인 (F)->(T)를 사용해야 되지 않을까 라고 생각했다.

 

우리의 목적은 일단 주어진 2-CNF식이 가능한지에 대해 판별해야 한다. 2-CNF식이 가능한지 판별하기 위해서는 위 간선들을 이용한 그래프에서 (xi) -> (-xi), (-xi) -> (xi) 경로가 있는지 파악하는 것이다. 위에서 설명한 것처럼 간선은 (F)->(T)로 시작 노드와 끝 노드의 조건이 반드시 만족되어야 한다. 그런데 (xi) -> (-xi), (-xi) -> (xi) 는 같은 xi의 경우가 반드시 참이고, 또 반드시 거짓이 공존해야 하므로 모순이 된다. 이를 구하기 위해서는 그래프의 SCC를 구해야 한다. 같은 SCC내에 xi, -xi가 공존한다면  (xi) -> (-xi), (-xi) -> (xi) 경로가 있다는 뜻이므로 모순이 존재한다는 뜻이다.

 

여기서 (xi) -> (-xi) 가 가능한 경로 하나만 있어도 모순이 아닌가? 라고 나도 생각했는데 내가 내린 결론은 SCC가 아니라면 중간 노드에서 옆으로 새거나 아예 (-xi) 에서 시작해 다른 그래프들을 돌며 x 경우들을 완성하는 경우가 생길 수 있기 때문이라고 생각했다.

 

반대로 생각하면 불가능이 자명한 입력 (i i), (-i -i)를 보면 간선은 (-xi) -> (xi) 와 (xi) -> (-xi) 간선 두개가 생긴다. 만약 입력이 (i i) 하나밖에 없다면 간선은 (-xi) -> (xi) 로 생길테지만 위 조건은 절대 불가능하지 않다.

 

그렇다면 실제 x1, x2, .. xi 의 T F 값은 어떻게 얻을 수 있을까? 하면 이것도 인터넷에서 찾아 알게 된 방법으로는 위상 정렬상 우선인 노드들에 대해 거짓 처리해 주면 된다고 한다. 처음엔 이해가 안갔지만 위의 언급한 (xi) -> (-xi) 경로 하나만 있을때를 생각해 보자.

 

i가 1일때, 그리고 노드가 1~3까지 있을때, (x1) -> (-x1) 일때 위상 정렬상으로 (x1)가 먼저 있다. 그런데 아까 말했듯이 (x1)를 무시하고 (F처리) 하고 (-x1)부터 시작한다면, 그리고 (-x1) -> (x2), (-x1) -> (x3) 이렇게 x1,x2,x3을 완성하는 것이 가능하다. 만약 x1을 T처리 한다면 (x1) -> (-x1)에서 성립하지 않으므로 끊길 것이다. 그러므로 위상 정렬 순서일때 먼저 만나는 노드의 경우에 대해 거짓 처리해야 모든 그래프를 돌며 가능한 경우를 만들 수 있다. 위 과정들은 내가 생각한 거라 정확하지 않을 수 있다.

import sys
sys.setrecursionlimit(999999)

N,M=map(int,sys.stdin.readline().rstrip().split())
graph=[[] for _ in range(2*N+1)]

for _ in range(M):
    a,b=map(int,sys.stdin.readline().rstrip().split())
    graph[-a].append(b)
    graph[-b].append(a)

parent=[10001 for _ in range(2*N+1)]
stack=[]
in_scc=[0 for _ in range(2*N+1)]
num=0
scc_num=0

def dfs(cur):
    global num
    global scc_num
    num+=1
    parent[cur]=num
    stack.append(cur)
    parent_compare=parent[cur]
    
    for new in graph[cur]: #자식노드 조사
        if parent[new]==10001: #미방문된 자식노드 DFS
            parent_compare=min(parent_compare,dfs(new))
        elif in_scc[new]==0: #방문됐다면 해당노드가scc가 아닐때 업데이트
            parent_compare=min(parent[new],parent_compare)
            
    if parent_compare==parent[cur]: #cur=SCC중 가장 parent넘버가 작은 노드
        scc_num+=1
        cur_scc=set()
        while 1:
            pop=stack.pop()
            cur_scc.add(pop)
            in_scc[pop]=scc_num
            if -pop in cur_scc:
                print(0)
                exit()
            if pop==cur:
                break
    return parent_compare

for i in range(N,-N-1,-1):
    if i==0:
        continue
    if parent[i]==10001:
        dfs(i)
print(1)

ans=[0 for _ in range(N+1)]

for i in range(1,N+1):
    if in_scc[i]<in_scc[-i]:
        ans[i]=1

for i in range(1,N+1):
    print(ans[i],end=' ')

 

저번에 SCC에서 이용한 dfs()함수를 사용했고, 만약 dfs()함수를 돌며 SCC를 찾는 도중에 임의의 노드 i, -i가 scc에 같이 있는 것이 확인 될 시 0을 출력하고 중지시켰다. 그리고 in_scc[노드] 에 scc를 발견한 순서대로 번호를 넣어 이후 위상 정렬을 간단하게 판별할 수 있도록 했다. 별 문제없이 dfs()를 돌며 SCC를 모두 찾았다면, in_scc[i]와 in_scc[-i]를 비교한다. in_scc[노드]의 숫자가 클 수록 나중에 방문했다는 뜻이고, 이는 위상 정렬 순위가 높다는 뜻이다. 그러므로 만약 in_scc[-i]가 더 클때 (위상 정렬 순위가 높을때) ans[i]는 참이 된다.