2-SAT 알고리즘 응용 문제 풀어보기 220827

백준 BOJ 11281번 : 2-SAT - 4

문제 난이도 : Platinum III

알고리즘 분류 : SCC, 2-SAT

 

2-SAT에 맞는 식이 주어질 때 x1 ~ xN에 참 또는 거짓을 넣어 식 전체가 참이 되도록 만들 수 있는지 판별하고, 만약 가능하다면 식을 참으로 만드는 각 변수 x1 ~ xN의 값으로 가능한 것을 하나 구하는 문제이다.

 

식을 참으로 만들 수 있는지 여부의 판별은 2-SAT - 3의 풀이와 동일하다.

이제 식을 만족시키는 각 변수의 참/거짓 값을 찾아야하는데, 그리디하게 접근해보자.

x → y라는 식이 거짓이 되는 경우는 x = true, y = false인 경우뿐이다.

x = false이면 y는 true든 false든 관계없다.

 

식을 최대한 참으로 만들기 위한 최선의 전략은 노드들을 연결했을 때 앞인 것에서부터 값들을 false로 만들어주면 된다는 것이다.

이 때 x = false라면, ~x = true이므로 반대에 해당하는 번호의 노드는 true로 체크해주면 된다.

 

그러면 이제 다음 문제는 연결 관계가 앞인 것부터 어떻게 접근하냐는 것인데, 이것은 SCC 알고리즘에 원리에 의해 쉽게 구현이 가능하다.

왜냐하면 dfs를 수행할 때 깊이가 깊은 것부터 scc 번호가 매겨졌으므로, scc 그룹의 번호가 큰 것이 위상적으로 앞에 위치하기 때문이다.

따라서 scc 번호를 기준으로 내림차순 정렬을 한 뒤, 앞에서부터 false를 매겨주면 된다.

 

 

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

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    adj.resize(N*2);

    while(M--) {
        int a, b; cin >> a >> b;

        if(a < 0) a = (-a)*2 - 2;
        else a = a*2 - 1;

        if(b < 0) b = (-b)*2 - 2;
        else b = b*2 - 1;

        int na, nb;

        if(a % 2 == 0) na = a + 1;
        else na = a - 1;

        if(b % 2 == 0) nb = b + 1;
        else nb = b - 1;

        adj[na].push_back(b);
        adj[nb].push_back(a);
    }

    nnum.resize(N*2);
    cnum.resize(N*2);
    ch.resize(N*2);

    for(int i=0; i<N*2; i++)
        if(nnum[i] == 0) dfs(i);

    bool check = true;

    for(int i=0; i<N; i++) {
        if(cnum[i*2] == cnum[i*2 + 1]) {
            check = false;
            break;
        }
    }

    if(check) cout << 1 << "\n";
    else {
        cout << 0 << "\n";
        return 0;
    }

    vector<pair<int, int>> p(N*2);
    for(int i=0; i<N*2; i++) p[i] = {cnum[i], i};

    sort(p.begin(), p.end(), greater<pair<int, int>>());

    vector<int> tf(N*2, -1);

    for(int i=0; i<N*2; i++) {
        int x = p[i].second;

        if(tf[x/2] == -1) {
            if(x % 2 == 1) tf[x/2] = 0;
            else tf[x/2] = 1;
        }
    }

    for(int i=0; i<N; i++) cout << tf[i] << " ";
    cout << "\n";
}

 

참고로 이 문제와 동일한 풀이 코드로 백준 BOJ 11278번 : 2-SAT - 2 문제를 풀이할 수 있다. (범위만 더 작음)

 

 

백준 BOJ 3648번 : 아이돌

문제 난이도 : Platinum III

알고리즘 분류 : SCC, 2-SAT

 

N명의 참가자에 대해 M명의 심사위원이 각각 두 명의 참가자에 대해 찬성, 반대를 하는데, 1번 참가자는 반드시 선발하면서 각 심사위원의 평가 중 최소 하나는 반영되도록 선발 멤버를 뽑을 수 있는지의 여부를 구하는 문제이다.

 

나머지는 기본적인 2-SAT 문제와 동일한데, 1번 참가자를 반드시 합격시키는 조건이 포함된다.

이것은 기존의 식에 (x1 ∨ x1) 절을 포함시켜서 해결이 가능하다. (그러면 x1이 반드시 참이 되어야하므로)

그러면 그래프를 연결해주어야 하는데, 양쪽 항이 동일하므로 ~x1 → x1 하나만 이어주면 된다. (아래의 풀이 코드에서는 adj[0].push_back(1);에 해당)

 

 

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

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M;

    while(cin >> N >> M) {
        adj.clear(); adj.resize(N*2);

        while(M--) {
            int a, b; cin >> a >> b;

            if(a < 0) a = (-a)*2 - 2;
            else a = a*2 - 1;

            if(b < 0) b = (-b)*2 - 2;
            else b = b*2 - 1;

            int na, nb;

            if(a % 2 == 0) na = a + 1;
            else na = a - 1;

            if(b % 2 == 0) nb = b + 1;
            else nb = b - 1;

            adj[na].push_back(b);
            adj[nb].push_back(a);
        }

        adj[0].push_back(1);

        nnum.clear(); nnum.resize(N*2);
        cnum.clear(); cnum.resize(N*2);
        ch.clear();   ch.resize(N*2);

        for(int i=0; i<N*2; i++)
            if(nnum[i] == 0) dfs(i);

        bool check = true;

        for(int i=0; i<N; i++) {
            if(cnum[i*2] == cnum[i*2 + 1]) {
                check = false;
                break;
            }
        }

        if(check) cout << "yes\n";
        else cout << "no\n";
    }
}

 

 

백준 BOJ 16915번 : 호텔 관리

문제 난이도 : Platinum III

알고리즘 분류 : SCC, 2-SAT

 

N개의 방이 각 2개의 스위치에 연결되어 있으며, M개의 스위치에 대해 연결되어 있는 방의 정보가 주어질 때, 스위치를 누르면 연결되어있는 방들의 문이 toggle (열려 있으면 닫히고, 닫혀 있으면 열림) 된다고 한다면 방의 초기 문의 상태가 주어졌을 때 주어진 스위치들만으로 방의 문을 열 수 있는지 묻는 문제이다.

 

각 방이 무조건 2개의 스위치에만 연결되어있다는 것이 포인트이다.

그러면 연결된 상태를 이용하여 2-SAT 문제로 치환시켜 생각할 수 있다.

예를 들어 어떤 방이 a번 스위치와 b번 스위치에 연결되어 있다고 할 때, 문이 열려있다면 두 스위치 모두 누르거나 누르지 않아야 하며 (a → b, ~a → ~b) 문이 닫혀있다면 둘 중 하나의 스위치만 눌러야 한다. (a → ~b, ~a → b)

이제 그래프 연결을 해주고 SCC를 돌린 뒤 기본적인 2-SAT 알고리즘 풀이대로 풀어주면 된다.

 

 

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

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int N, M; cin >> N >> M;

    vector<int> v(N+1);
    for(int i=1; i<=N; i++) cin >> v[i];

    vector<vector<int>> u(N+1);

    for(int i=1; i<=M; i++) {
        int K; cin >> K;

        while(K--) {
            int x; cin >> x;

            u[x].push_back(i);
        }
    }

    adj.resize(M*2);

    for(int i=1; i<=N; i++) {
        int a = u[i][0]*2 - 1, b = u[i][1]*2 - 1;

        int na = a - 1, nb = b - 1;

        if(v[i] == 0) {
            adj[a].push_back(nb);
            adj[b].push_back(na);
            adj[na].push_back(b);
            adj[nb].push_back(a);
        }
        else {
            adj[a].push_back(b);
            adj[b].push_back(a);
            adj[na].push_back(nb);
            adj[nb].push_back(na);
        }
    }

    nnum.resize(M*2);
    cnum.resize(M*2);
    ch.resize(M*2);

    for(int i=0; i<M*2; i++)
        if(nnum[i] == 0) dfs(i);

    bool check = true;

    for(int i=0; i<M; i++) {
        if(cnum[i*2] == cnum[i*2 + 1]) {
            check = false;
            break;
        }
    }

    if(check) cout << 1 << "\n";
    else cout << 0 << "\n";
}

 

 

백준 BOJ 7535번 : A Bug's Life

문제 난이도 : Gold II

알고리즘 분류 : 그래프 탐색 (SCC, 2-SAT)

 

N마리의 벌레가 있고, M개의 상호작용 쌍이 주어질 때, 서로 다른 성별의 벌레들끼리만 상호작용을 한다면 주어진 벌레들 중에서 규칙을 어기는 벌레가 있었는지 검사하는 문제이다.

 

N마리의 성별을 bool 변수로 잡고 true면 수컷, false면 암컷이라고 하면 2-SAT 문제가 된다.

a b가 상호작용을 했다면 a가 수컷이라면 b는 암컷이고, a가 암컷이라면 b는 수컷이다.

따라서 a → ~b, b → ~a, ~a → b, ~b → a라는 4개의 명제가 얻어진다.

이제 SCC와 2-SAT 알고리즘으로 풀이해주면 된다.

 

 

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

vector<vector<int>> adj, scc;
vector<int> nnum, cnum;
int ncnt = 0, ccnt = 0;

stack<int> s;
vector<bool> ch;

int dfs(int x) {
    nnum[x] = ++ncnt;
    s.push(x);

    int tmp = nnum[x];

    for(int i=0; i<adj[x].size(); i++) {
        int y = adj[x][i];

        if(nnum[y] == 0) tmp = min(tmp, dfs(y));
        else if(!ch[y]) tmp = min(tmp, nnum[y]);
    }

    if(tmp == nnum[x]) {
        vector<int> v;
        ccnt++;

        while(true) {
            int y = s.top();
            s.pop();

            v.push_back(y);

            ch[y] = true;
            cnum[y] = ccnt;

            if(y == x) break;
        }

        sort(v.begin(), v.end());

        scc.push_back(v);
    }

    return tmp;
}

main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL), cout.tie(NULL);

    int T; cin >> T;

    for(int t=1; t<=T; t++) {
        int N, M; cin >> N >> M;

        adj.clear(); adj.resize(N*2);

        while(M--) {
            int a, b; cin >> a >> b;

            if(a < 0) a = (-a)*2 - 2;
            else a = a*2 - 1;

            if(b < 0) b = (-b)*2 - 2;
            else b = b*2 - 1;

            int na, nb;

            if(a % 2 == 0) na = a + 1;
            else na = a - 1;

            if(b % 2 == 0) nb = b + 1;
            else nb = b - 1;

            adj[a].push_back(nb);
            adj[b].push_back(na);

            adj[na].push_back(b);
            adj[nb].push_back(a);
        }

        nnum.clear(); nnum.resize(N*2);
        cnum.clear(); cnum.resize(N*2);
        ch.clear();   ch.resize(N*2);

        for(int i=0; i<N*2; i++)
            if(nnum[i] == 0) dfs(i);

        bool check = true;

        for(int i=0; i<N; i++) {
            if(cnum[i*2] == cnum[i*2 + 1]) {
                check = false;
                break;
            }
        }

        cout << "Scenario #" << t << ":\n";

        if(check) cout << "No suspicious bugs found!\n\n";
        else cout << "Suspicious bugs found!\n\n";
    }
}