BOJ 2416 - 문 링크
(2023.07.13 기준 P3)

문제

문이 2개가 있는 수로가 N개가 주어지고 스위치 M개가 주어진다. 각 문은 스위치의 상태에 따라 열리거나 닫히며, 수로의 두 문 중 하나만 닫혀도 수로는 닫히는 것이다. 이 때, 모든 수로를 닫는 것이 가능한지 판별 및 가능할 때의 스위치 상태 출력

알고리즘

2-SAT

풀이

두 문 중 하나만 닫혀도 되는 것은 곧 (a or b) 절과 같은 말이다. 모든 수로가 닫혀야 하므로 (a1 or b1) and (a2 or b2) and ... and (an or bn) 이므로 아주 전형적인 2-CNF다.

스위치가 켜진 상태를 참, 꺼진 상태를 거짓으로 두고 SCC를 만들어 참과 거짓의 위상 정렬 상 순서를 확인하면 된다.

주의사항

메모리 제한이 아주 타이트하다. 그래서 Python에선 코사리주로 SCC를 만들 경우 MLE가 난다.
그러므로 타잔으로 구현하자.

나는 C++은 코사리주, Python은 타잔으로 구현했다.

풀이

• C++

#include <bits/stdc++.h>
using namespace std;

const int MAXM = 500000;

int N, M, a, sa, b, sb;

int Not(int a){
    if (a <= M) return a + M;
    return a - M;
}

// strongly connected component
struct SCC{
    vector<int> graph[MAXM * 2 + 1], reverse_graph[MAXM * 2 + 1];
    stack<int> stk;
    bool visited[MAXM * 2 + 1];
    int ids[MAXM * 2 + 1], idx;

    void _dfs(int i){ // 정방향 탐색으로 정점 쌓기
        visited[i] = true;
        for (auto j: graph[i]) if (!visited[j]) _dfs(j);
        stk.push(i);
    }

    void _reverse_dfs(int i){ // 역방향 탐색으로 SCC 찾기
        visited[i] = true;
        ids[i] = idx;
        for (auto j: reverse_graph[i]) if (!visited[j]) _reverse_dfs(j);
    }

    void kosaraju(){ // get SCC
        fill(visited + 1, visited + M * 2 + 1, false);
        for (int i = 1, MM = M * 2; i <= MM; i++) if (!visited[i]) _dfs(i);

        fill(ids + 1, ids + M * 2 + 1, -1); idx = 0;
        fill(visited + 1, visited + M * 2 + 1, false);
        while (!stk.empty()){
            int i = stk.top(); stk.pop();
            if (!visited[i]) _reverse_dfs(i), idx++;
        }
    }

    void check(){
        vector<int> result;
        for (int i = 1; i <= M; i++){
            // 역과 같은 SCC에 속하면 모순(거짓)
            if (ids[i] == ids[Not(i)]){
                cout << "IMPOSSIBLE";
                return;
            }
            // 위상 정렬 순서 상 빠른 것이 False
            result.push_back(ids[i] > ids[Not(i)]);
        }

        for (auto x: result) cout << x << '\n';
    }
};

// two_sat
struct TS{
    SCC scc;

    void _add(int a, int b){
        scc.graph[a].push_back(b);
        scc.reverse_graph[b].push_back(a);
    }

    void add_and(int a){ // ... and a
        int _a = Not(a);
        _add(_a, a);
    }

    void add_or(int a, int b){ // ... and (a or b)
        int _a = Not(a), _b = Not(b);
        _add(_a, b); _add(_b, a);
    }

    void check(){ // SCC를 구한 후 모순인지 확인 및 변수 값 출력
        scc.kosaraju();
        scc.check();
    }
}ts;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> N >> M;

    while (N--){
        cin >> a >> sa >> b >> sb;

        // 스위치가 켜져야 하면 a, 꺼져야 하면 ￢a
        if (!sa) a = Not(a);
        if (!sb) b = Not(b);

        // 스위치 a의 상태나 스위치 b의 상태 중 하나를 만족해야 수로가 닫힌다.
        ts.add_or(a, b);
    }

    ts.check();
}

• Python

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

def Not(a):
    if a <= M:
        return a + M
    return a - M

# strongly connected component
class SCC:
    def __init__(self):
        self.graph = [[] for _ in range(M * 2 + 1)]

    def _dfs(self, i):
        min_idx = self.ids[i] = self.idx
        self.idx += 1
        self.stk.append(i)

        # 사이클이 도는 정점을 모두 같은 번호로
        # 사이클 중 가장 번호가 작은 값으로 scc를 이룸
        for j in self.graph[i]:
            if not ~self.ids[j]:
                min_idx = min(min_idx, self._dfs(j))
            elif not ~self.scc_ids[j]:
                min_idx = min(min_idx, self.ids[j])

        # 지금 번호가 사이클을 이루는 번호(가장 작은 번호)이면
        # 그 번호까지 stk에서 꺼내서 scc를 이루게 함.
        if self.ids[i] == min_idx:
            # scc = []
            while True:
                j = self.stk.pop()
                self.scc_ids[j] = self.scc_idx
                # scc.append(j)
                if i == j:
                    break
            # scc_lst.append(scc)
            self.scc_idx += 1

        return min_idx

    def tarjan(self): # get SCC
        self.stk = []
        self.ids = [-1] * (M * 2 + 1); self.idx = 0
        self.scc_ids = [-1] * (M * 2 + 1); self.scc_idx = 0
        for i in range(1, M * 2 + 1):
            if not ~self.ids[i]:
                self._dfs(i)

    def check(self):
        result = []
        for i in range(1, M + 1):
            # 역과 같은 SCC에 속하면 모순(거짓)
            if self.scc_ids[i] == self.scc_ids[Not(i)]:
                print('IMPOSSIBLE')
                return
            # scc 번호는 위상 정렬의 역순. 위상 정렬 순서 상 빠른 것이 False
            # 즉, scc 번호가 높은 것이 False
            result.append(int(self.scc_ids[i] < self.scc_ids[Not(i)]))

        print(*result, sep = '\n')

class TS: # two_sat
    def __init__(self):
        self.scc = SCC()

    def _add(self, a, b):
        self.scc.graph[a].append(b)

    def add_and(self, a): # ... and a
        _a = Not(a)
        self._add(_a, a)

    def add_or(self, a, b): # ... and (a or b)
        _a = Not(a); _b = Not(b)
        self._add(_a, b)
        self._add(_b, a)

    def check(self): # SCC를 구한 후 모순인지 확인 및 변수 값 출력
        self.scc.tarjan()
        self.scc.check()

N, M = map(int, input().split())

ts = TS()
for _ in range(N):
    a, sa, b, sb = map(int, input().split())

    # 스위치가 켜져야 하면 a, 꺼져야 하면 ￢a
    if not sa:
        a = Not(a)
    if not sb:
        b = Not(b)

    # 스위치 a의 상태나 스위치 b의 상태 중 하나를 만족해야 수로가 닫힌다.
    ts.add_or(a, b)

ts.check()