백준 2416번: 문 (C++)

https://www.acmicpc.net/problem/2416

2416번: 문

---

Solved By: 2-SAT, SCC

 

메모리 초과가 계속 나서 최대한의 최적화를 해보려 했지만 원인이 무엇인지 알 수 없었습니다.

그러다가 바보같이 SCC를 구하여 담아두는 2차원 vector배열이 필요 없다는 것을 알아내어 맞출 수 있었습니다.

2-SAT은 결국 각 변수가 몇 번째 SCC에 속하는지만 알고 있으면 된다는 걸 깨닫습니다. (물론 이 문제에 한정해서입니다.)

 

문제 해석:

각 수로에는 문의 열고, 닫고를 책임지는 스위치가 2개 있습니다. 수로에 물이 통하지 않기 위해서는 적어도 하나의 수로만 닫혀있으면 됩니다.

즉, 한 수로를 Clause하나라고 볼 수 있고, 각각의 문을 책임지는 스위치가 변수라고 할 수 있습니다.

(ex: 2번 스위치라면 2번 문이 있는 수로와 연관이 있습니다.)

 

이대로 2-SAT을 하여 답을 구할 수 있겠다고 생각하지만, 이 문제에서 F -> F == true라고 처리해버린다면 문이 다 오픈된 상태이기 때문에 무조건 모든 명제를 T -> T == true로 해야 합니다. (T -> F == false라서 안 됨.)

 

#include <iostream>
#include <vector>
#include <stack>
#include <algorithm>
#define MAX 1000002
#define pii pair<int, int>
using namespace std;

int n, m;
vector<int> adj[MAX];
stack<int> s;
vector<int> visitedOrder(MAX, -1);
vector<int> sccNum(MAX, -1);
vector<pii> satOrder;
int order = 0, sccCnt = 0;

int dfs(int now){
    int minOrder = visitedOrder[now] = ++order;
    s.push(now);
    
    for(int i = 0; i < adj[now].size(); i++){
        int next = adj[now][i];
        
        if(visitedOrder[next] == -1){
            minOrder = min(minOrder, dfs(next));
        }
        else if(sccNum[next] == -1){
            minOrder = min(minOrder, visitedOrder[next]);
        }
    }
    
    if(visitedOrder[now] == minOrder){
        while(true){
            int temp = s.top(); s.pop();
            sccNum[temp] = sccCnt;
            satOrder.push_back({temp, sccNum[temp]});
            if(temp == now) break;
        }
        
        sccCnt++;
    }
    
    return minOrder;
}

void tarjan(){
    for(int i = 2; i <= 2 * m + 1; i++){
        if(visitedOrder[i] == -1) dfs(i);
    }
}

bool cmp(pii a, pii b){
    return a.second > b.second;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> n >> m;
    for(int i = 0; i < n; i++){
        int a, sa, b, sb;
        cin >> a >> sa >> b >> sb;
        int not_a, not_b;
        
        if(sa == 0){ // 스위치가 닫혀야 문이 닫힌다.
            a *= 2;
            not_a = a + 1;
        }
        else{ // 스위치를 켜야 문이 열린다
            a = (a * 2) + 1;
            not_a = a - 1;
        }
        
        if(sb == 0){
            b *= 2;
            not_b = b + 1;
        }
        else{
            b = (b * 2) + 1;
            not_b = b - 1;
        }
        
        adj[not_a].push_back(b);
        adj[not_b].push_back(a);
    }
    
    tarjan();
    
    for(int i = 2; i <= 2 * m; i += 2){
        if(sccNum[i] == sccNum[i + 1]){
            cout << "IMPOSSIBLE";
            return 0;
        }
    }
    
    
    sort(satOrder.begin(), satOrder.end(), cmp);
       
    vector<int> answer(m + 1, -1);
    
    for(auto p : satOrder){
        int vertex = p.first;
        int varIdx = vertex / 2;
        int isTrue = (vertex % 2 == 0);
        
        if(answer[varIdx] != -1) continue;
        
        // 이 문제에서는 false -> false는 문이 모두 열려있는 상태다.
        // 즉, true -> true가는 방법을 택해야 한다.
        answer[varIdx] = isTrue;
    }
    
    for(int i = 1; i < answer.size(); i++){
        cout << answer[i] << '\n';
    }
    
    return 0;
}