정말 공부하기 꺼려지던 2-SAT을 공부했는데.. 별거 없더라?
바로 제일 쉬운 2-SAT 문제 풀이를 올려보겠다.

BOJ 11280 - 2-SAT - 3 링크
(2022.12.26 기준 P4)
(치팅은 나빠요)

문제

N개의 변수, M개의 절로 이루어진 2-CNF 식 f가 있을 때, 식 f를 참으로 만들 수 있으면 1 아니면 0 출력

알고리즘

문제 그대로 2-SAT 문제다.

풀이

2-SAT을 아예 모른다면 이 블로그에서 공부하고 오자.

2-SAT에서 (i v j) 절이 있다고 하자. 이 절은 곧 ¬i -> j, ¬j -> i이 된다. 왜냐면, 하나가 거짓이면 나머지 하나는 무조건 참이어야 하므로.

그러므로 절이 주어질 때마다, ¬i -> j, ¬j -> i인 두 간선을 그래프로 만들어주자.
그리고 SCC를 찾자.
만약, 어떤 한 변수와 그 변수의 역이 같은 SCC에 있으면 모순이 되는 것이다. 결국 (¬i -> i -> ¬i) 사이클은 모순이니깐.

정리하자면 2-SAT은 모든 절이 참인 식이고 모든 절은 or로 이루어져 있다.
만약 하나가 거짓이면 나머지 하나는 참이어야 하는 것은 자명하다. 그러므로 이를 그래프 간선으로 나타내고, 모든 변수마다 자신의 역과 같은 SCC에 포함되어 있는지 확인하면 된다.

코드

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(100000)

def dfs(here):
    visited[here] = True
    for there in graph[here]:
        if not visited[there]:
            dfs(there)
    queue.append(here)

def reverse_dfs(here):
    visited[here] = True
    ids[here] = idx
    for there in reverse_graph[here]:
        if not visited[there]:
            reverse_dfs(there)

N, M = map(int, input().split())
graph = [[] for _ in range(N * 2 + 1)] # 그래프
reverse_graph = [[] for _ in range(N * 2 + 1)] # 역방향

# i v j : ¬i -> j, ¬j -> i
# 둘 중 하나가 거짓이면 하나는 무조건 참이어야 하기 때문.
for _ in range(M):
    i, j = map(int, input().split())
    graph[-i].append(j)
    reverse_graph[j].append(-i)
    graph[-j].append(i)
    reverse_graph[i].append(-j)

# 코사리주
# 정방향 탐색으로 정점 쌓기
queue = []
visited = [False] * (N * 2 + 1)
for here in range(1, N * 2 + 1):
    if not visited[here]:
        dfs(here)
# 역방향 탐색으로 SCC 찾기
visited = [False] * (N * 2 + 1)
ids = [-1] * (N * 2 + 1)
idx = 0
while queue:
    here = queue.pop()
    if not visited[here]:
        reverse_dfs(here)
        idx += 1

# 모든 변수는 역과 같은 SCC이면 안된다. 즉, 모순인지 찾아야 한다.
for i in range(1, N + 1):
    if ids[i] == ids[-i]:
        print(0)
        break
else:
    print(1)

• C++

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
vector<int> graph[20001], reverse_graph[20001], queue;
bool visited[20001];
int ids[20001];

void dfs(int here){
    visited[here] = true;
    for (auto there: graph[here]) if (!visited[there]) dfs(there);
    queue.push_back(here);
}

void reverse_dfs(int here, int idx){
    visited[here] = true;
    ids[here] = idx;
    for (auto there: reverse_graph[here]) if (!visited[there]) reverse_dfs(there, idx);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    int N, M, i, not_i, j, not_j;
    cin >> N >> M;

    /* i v j : ¬i -> j, ¬j -> i
    둘 중 하나가 거짓이면 하나는 무조건 참이어야 하기 때문. */
    while (M--){
        cin >> i >> j;
        if (i < 0){
            not_i = -i;
            i = N - i;
        }
        else not_i = N + i;
        if (j < 0){
            not_j = -j;
            j = N - j;
        }
        else not_j = N + j;
        graph[not_i].push_back(j);
        reverse_graph[j].push_back(not_i);
        graph[not_j].push_back(i);
        reverse_graph[i].push_back(not_j);
    }

    /* 코사리주 */
    /* 정방향 탐색으로 정점 쌓기 */
    memset(visited, false, sizeof(visited));
    int here;
    for (here = 1; here <= N * 2; here++) if (!visited[here]) dfs(here);
    /* 역방향 탐색으로 SCC 찾기 */
    memset(visited, false, sizeof(visited));
    int idx = 0, sz = queue.size();
    while (sz--){
        here = queue.back();
        queue.pop_back();
        if (!visited[here]){
            reverse_dfs(here, idx++);
        }
    }

    /* 모든 변수는 역과 같은 SCC이면 안된다. 즉, 모순인지 찾아야 한다. */
    for (int i = 1; i <= N; i++){
        if (ids[i] == ids[i + N]){
            cout << 0;
            return 0;
        }
    }
    cout << 1;
}

여담

2-SAT에 왜 그렇게 쫄았을까? 되게 간단한 알고리즘인 듯 하다.
오늘 공부했는데 바로 이해가 가버렸다구 푸하핳