BOJ 1739 도로 정비하기

도로 정비하기
(http://boj.kr/1739)

각 가로도로와 세로도로를 하나의 변수로 생각한다.
\(i\)번 가로도로를 \(W_i\), \(i\)번 세로도로를 \(H_i\)라고 할 때,
이 도로들이 가질 수 있는 방향은 두 가지이므로 참과 거짓의 불리언 값을 가진다고 생각할 수 있다.

버스가 \((W_i,H_i)\)에서 \((W_j,H_j)\)로 운행한다 했을 때,
가장 간단한 경우인 \(W_i<W_j\)면서 \(H_i<H_j\)일 때를 보자.
변수가 참일 때 오른쪽 또는 아래, 거짓일 때 왼쪽 또는 위로 향한다고 해보자.
그러면 \((W_i\land H_j)\lor (H_i\land W_j)\)여야지 버스를 운행할 수 있다.
이 식을 2-CNF로 바꾸면,
\((W_i\lor H_i)\land (W_i\lor W_j)\land (H_j\lor H_i)\land (H_j\lor W_j)\)가 된다.
나머지 경우도 마찬가지로, 반대 방향으로 가는 경로는 \(\lnot\)이 붙어있다고 생각하고 처리하면 된다.

이제 2-SAT 문제가 됐으니 풀면 된다.

#include <bits/stdc++.h>
 
using namespace std;
 
vector<int> gph[4001];
int num[4001], cnt, grpn[4001];
bool com[4001];
stack<int> stk;
vector<vector<int> > grp;
 
int f(int now) {
    num[now] = ++cnt;
 
    stk.push(now);
 
    int ret = num[now];
    for (int nxt : gph[now]) {
        if (num[nxt] == 0)
            ret = min(ret, f(nxt));
        else if (!com[nxt])
            ret = min(ret, num[nxt]);
    }
 
    if (ret == num[now]) {
        vector<int> tmpv;
        while (true) {
            int tmp = stk.top();
            stk.pop();
 
            grpn[tmp] = grp.size() + 1;
            com[tmp] = true;
            tmpv.push_back(tmp);
 
            if (tmp == now)
                break;
        }
        grp.push_back(tmpv);
    }
 
    return ret;
}
 
int main() {
    int t;
    scanf("%d", &t);
    while (t--) {
        for (int i = 0;i <= 4000;++i) {
            gph[i].clear();
            num[i] = 0;
            grpn[i] = 0;
            com[i] = false;
        }
        cnt = 0;
        grp.clear();
 
        int n, m, k;
        scanf("%d %d %d", &n, &m, &k);
        while (k--) {
            pair<int, int> u, v;
            scanf("%d %d %d %d", &u.first, &u.second, &v.first, &v.second);
 
            int a, b, c, d, na, nb, nc, nd;
 
            if (u == v)
                continue;
            
            if (u.first < v.first) {
                a = u.second;
                na = m + u.second;
                c = v.second;
                nc = m + v.second;
            }
            else {
                a = m + u.second;
                na = u.second;
                c = m + v.second;
                nc = v.second;
            }
 
            if (u.second < v.second) {
                b = 2000 + v.first;
                nb = 2000 + n + v.first;
                d = 2000 + u.first;
                nd = 2000 + n + u.first;
            }
            else {
                b = 2000 + n + v.first;
                nb = 2000 + v.first;
                d = 2000 + n + u.first;
                nd = 2000 + u.first;
            }
 
            gph[na].push_back(c);
            gph[na].push_back(d);
            gph[nb].push_back(c);
            gph[nb].push_back(d);
            gph[nc].push_back(a);
            gph[nc].push_back(b);
            gph[nd].push_back(a);
            gph[nd].push_back(b);
        }
 
        for (int i = 1;i <= m * 2;++i)
            if (num[i] == 0)
                f(i);
        for (int i = 2001;i <= 2000 + n * 2;++i)
            if (num[i] == 0)
                f(i);
 
        bool can = true;
        for (int i = 1;i <= m;++i)
            if (grpn[i] == grpn[m + i])
                can = false;
        for (int i = 2001;i <= 2000 + n;++i)
            if (grpn[i] == grpn[n + i])
                can = false;
 
        printf("%s\n", can ? "Yes" : "No");
    }
 
    return 0;
}