백준 2519 막대기 C++

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

 

2-SAT 관련 문제입니다. 명제를 정의하는데 시간을 많이 썼지만, 실질적인 구현은 크게 어렵지 않습니다. 

 

주어진 문제를 보면, N명의 사람들이 3개의 막대기를 갖고 있고, 각자 최대 1개의 막대기를 뺄 수 있습니다. 이 때 막대기를 뺀 상태에서 모든 막대기가 겹치는지, 겹치지 않는다면 무엇을 뺀 것인지를 구하는 문제입니다. 

 

문제를 2-SAT 문제로 대입하면 다음과 같습니다. 

2-SAT : (x1 or x2) and (x3 or x4) and .... 와 같은 CNF 에서 명제가 true가 되는 x1, x2, ... 의 해를 구할 수 있는가

문제 : 모든 막대기들이 겹치지 않는가

 

즉, clause에 해당하는 것은 각 막대기들이 겹칠 때 뺄지 말지입니다.

x, y 라는 막대기가 있을 때, x의 state를 "x를 뺀다" 가 true, "x를 그대로 둔다" 가 false로 잡으면 2-SAT에 대입할 수 있습니다. 

겹치는 막대기를 대상으로 x 또는 y를 뺀다 == x or y 이므로, 모든 겹치는 막대기를 대상으로 (x1 or x2) and (x1 or x3) and .... 로 표현할 수 있습니다. (각 clause가 모두 true일 때 == 모든 겹치는 막대기 2개를 대상으로 적어도 하나를 뺀다)

 

하지만 조건이 하나 더 있습니다. 그것은 한 명 당 본인의 막대기 중 최대 1개를 뺄 수 있는 것입니다. 

이는 적어도 2개 이상의 막대를 그대로 둔다이며, 그러기 위해서는 2개의 막대기를 모두 뺄 수 없는 것입니다. 

즉, ~x or ~y에 해당됩니다. ( ~(x and y) == ~x or ~y )

( ~x or ~y == true <=> x를 두거나 (false) y를 두거나 (false) )

3개의 모든 본인 막대기 x, y, z에 대입하면 (~x or ~y) and (~y or ~z) and (~z or ~x) 이므로 CNF를 만족하고, 2-SAT에 대입할 수 있습니다. 

 

따라서 앞서 2개의 조건을 아래와 같이 변형하여 2-SAT 문제를 풀면됩니다. 

state x == True : x를 뺀다. False : x 안 뺀다.

1) 겹치는 막대기들을 대상으로 (x or y) 

2) 본인 막대기들을 대상으로 (~x or ~y) and (~y or ~z) and (~z or ~x) 

 

코드는 다음과 같습니다. (겹치는지 유무는 CCW로, 2-SAT 해결은 코사라주 알고리즘 SCC를 적용했습니다.)

#include <iostream>
#include <vector>
#include <stack>

using namespace std;

// state x == T : x 뺀다 F : x 그대로 둔다
// (a or b) == T : a 또는 b를 뺀다 
// 겹치는 거 대상으로 CNF 구성
// 각 사람은 3개 중 최대 1개 뺄 수 있으므로 ~(a and b) == T : a, b 모두 그대로 둔다
// 이므로 (~a or ~b) and (~a or ~c) and (~b or ~c) == T : a, b, c 중 최대 1개만 뺀다 

// 2-sat : a or b == ~a -> b / ~b -> a
// 입력값 대상으로 겹치는 거 + 본인 거 대상으로 그래프 생성

// 겹치는 지 유무 : ccw로 체크 (외적 방향 다르면 겹치는 거)

int N;
int MAX_N = 3000;
pair<pair<int, int>, pair<int, int>> sticks[3001];
vector<int> graph[6001];
vector<int> invGraph[6001];
bool visited[6001];
bool invVisited[6001];
stack<int> stk;
int sccIdx[6001];

void init() {
    cin >> N;
    int x1, y1, x2, y2;
    for(int i = 1; i <= 3 * N; i++) {
        cin >> x1 >> y1 >> x2 >> y2;
        sticks[i] = {{x1, y1}, {x2, y2}};
    }
}

void makeGraphWithOwnSticks() {
    // 자기가 갖고 있는 거 대상으로 그래프 그리기 
    // (~a or ~b) and (~a or ~c) and (~b or ~c)
    // a or b == ~a -> b / ~b -> a
    // ~a or ~b == a -> ~b / b -> ~a
    int a, b, c, na, nb, nc;
    for(int i = 1; i <= 3 * N; i += 3) {
        a = i;
        na = MAX_N + a;
        b = i + 1;
        nb = MAX_N + b;
        c = i + 2;
        nc = MAX_N + c;

        // ~a or ~b
        graph[a].push_back(nb);
        invGraph[nb].push_back(a);
        graph[b].push_back(na);
        invGraph[na].push_back(b);

        // ~b or ~c
        graph[b].push_back(nc);
        invGraph[nc].push_back(b);
        graph[c].push_back(nb);
        invGraph[nb].push_back(c);

        // ~c or ~a
        graph[c].push_back(na);
        invGraph[na].push_back(c);
        graph[a].push_back(nc);
        invGraph[nc].push_back(a);
    }
}

bool CCW(pair<pair<int, int>, pair<int, int>> &p1, pair<pair<int, int>, pair<int, int>> &p2) {
    // p1 기준, p2 대상으로 외적, p2 기준, p1 대상으로 외적 계산해서
    // 모두 다른 방향이면 겹치는 거 
    // 2차원이므로 z 빼고 계산해도 됨. 그리고 일직선인 케이스는 신경 안 써도 됨 (입력에 없음)

    // p1 기준
    pair<int, int> v1 = {p1.second.first - p1.first.first, p1.second.second - p1.first.second};
    pair<int, int> v2 = {p2.second.first - p1.second.first, p2.second.second - p1.second.second};
    pair<int, int> v3 = {p2.first.first - p1.second.first, p2.first.second - p1.second.second};

    bool chk1 = ((v1.first * v2.second) - (v1.second * v2.first) > 0);
    bool chk2 = ((v1.first * v3.second) - (v1.second * v3.first) > 0);

    // 같으면 안 겹침 
    if(chk1 == chk2) return false;

    // p2 기준 
    v1 = {p2.second.first - p2.first.first, p2.second.second - p2.first.second};
    v2 = {p1.second.first - p2.second.first, p1.second.second - p2.second.second};
    v3 = {p1.first.first - p2.second.first, p1.first.second - p2.second.second};

    chk1 = ((v1.first * v2.second) - (v1.second * v2.first) > 0);
    chk2 = ((v1.first * v3.second) - (v1.second * v3.first) > 0);

    if(chk1 == chk2) return false;

    return true;
}

void makeGraphWithCrossedSticks() {
    // 겹치는 거 대상으로 그래프 추가
    // a or b == ~a -> b / ~b -> a
    int a, b, na, nb;
    for(int i = 1; i <= 3 * N; i++) {
        for(int j = i + 1; j <= 3 * N; j++) {
            bool isCrossed = CCW(sticks[i], sticks[j]);
            if(isCrossed == false) continue;

            a = i;
            b = j;
            na = MAX_N + a;
            nb = MAX_N + b;

            // ~a -> b
            graph[na].push_back(b);
            invGraph[b].push_back(na);
            // ~b -> a 
            graph[nb].push_back(a);
            invGraph[a].push_back(nb);
        }
    }
}

void makeGraph() {
    makeGraphWithOwnSticks();
    makeGraphWithCrossedSticks();
}

void dfs(int node) {
    if(visited[node]) return;
    
    visited[node] = true;
    for(auto v : graph[node]) {
        if(visited[v]) continue;
        dfs(v);
    }

    stk.push(node);
}

void invDfs(int node, int idx) {
    if(invVisited[node]) return;

    invVisited[node] = true;
    sccIdx[node] = idx;

    for(auto v : invGraph[node]) {
        if(invVisited[v]) continue;
        invDfs(v, idx);
    }
}

void SCC() {
    // 스택에 촥촥
    for(int i = 1; i <= 3 * N; i++) {
        dfs(i);
        dfs(MAX_N + i);
    }

    // 스택에 있는 거 대상으로 scc 만들기 
    // idx : scc idx
    int idx = 0;
    while(!stk.empty()) {
        int node = stk.top();
        stk.pop();

        if(invVisited[node]) continue;

        invDfs(node, idx);
        idx++;
    }
}

void calc() {
    // scc 구한 거 대상으로 x, ~x 같은 scc면 모순이므로 안 되는 케이스
    // 그런 거 없으면 위상정렬 순으로 x -> ~x : x = false, ~x -> x : x = true 
    int x, nx;
    for(int i = 1; i <= 3 * N; i++) {
        x = i;
        nx = MAX_N + x;
        if(sccIdx[x] == sccIdx[nx]) {
            cout << -1;
            return;
        }
    }

    vector<int> result;

    for(int i = 1; i <= 3 * N; i++) {
        x = i;
        nx = MAX_N + x;
        if(sccIdx[x] < sccIdx[nx]) {
            // x = false case 
            continue;
        } else {
            // x = true case 
            result.push_back(x);
        }
    }

    cout << result.size() << '\n';
    for(auto v : result) {
        cout << v << ' ';
    }
}

int main() {
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    init();
    makeGraph();
    SCC();
    calc();
}