[백준 15675] 괴도 강산

문제

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

 

알고리즘

2-SAT

 

풀이

강산이가 보석을 훔치기 위해선 행 또는 열에 한 번만 입장을 해야 합니다. 관장 택희가 보석이 도난당할 시, 즉시 경비원을 출동시키기 때문에 두 번 다시 입장이 불가능하기 때문입니다. 훔치는 과정에서 위치추적기를 얻을 시에는 언젠가는 다시 한번 방문을 해서 위치추적기를 떼어 놓아야만 합니다.

즉 박물관 좌표 $y$행,$x$열에 대하여 보석이 위치한 곳에는 $(T(y)\cap F(x))\cup (F(y)\cap T(x))$ 를 만족하며 추적기가 위치한 곳에 대해서는 $(T(y)\cap T(x))\cup (F(y)\cap F(x))$ 를 만족합니다. $T()$는 해당 행 또는 열을 방문한다는 의미이며 $F()$는 방문하지 않는다는 의미입니다. 위 두 식은 2-CNF형태를 만족하지 못하므로 전개를 통해 변형해주도록 합시다.

 

코드

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

#define T(x) (x<<1)
#define F(x) (x<<1|1)

int n, m, VC, SC;
char x;

vector<vector<int>> adj;
vector<int> discovered, sccid;
stack<int> st;
int scc(int here) {
    int ret = discovered[here] = VC++;
    st.emplace(here);

    for (auto there : adj[here]) {
        if (discovered[there] == -1) ret = min(ret, scc(there));
        else if (sccid[there] == -1) ret = min(ret, discovered[there]);
    }

    if (ret == discovered[here]) {
        while (1) {
            int t = st.top();
            st.pop();
            sccid[t] = SC;
            if (t == here) break;
        }
        SC++;
    }
    return ret;
}

void OR(int A, int B) {
    adj[A ^ 1].emplace_back(B);
    adj[B ^ 1].emplace_back(A);
}

void AOA(int a, int b, int c, int d) {//And or And. 2-CNF형태로 변형
    OR(a, c);    OR(a, d);
    OR(b, c);    OR(b, d);
}

int main() {
    FAST;
    cin >> n >> m;
    adj.resize((n + m) << 1);
    rep(i, n) rep(j, m) {
        int Y = i;
        int X = n + j;
        cin >> x;
        if (x == '#') AOA(T(Y), T(X), F(Y), F(X));
        else if (x == '*') AOA(T(Y), F(X), F(Y), T(X));
    }
    discovered = sccid = vector<int>((n + m) << 1, -1);
    rep(i, (n + m) << 1) if (discovered[i] == -1) scc(i);
    bool flag = true;
    rep(i, n + m) if (sccid[T(i)] == sccid[F(i)]) {
        flag = false;
        break;
    }
    cout << flag;

    return 0;
}