백준 11281번: 2-SAT - 4 (C++)

접근

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

11281번: 2-SAT - 4

이전 문제인 백준 11280번: 2-SAT - 3 문제에서 조금 더 발전한 문제로써 기존에 풀었던 문제의 코드에 변수들의 true/false 정보를 출력하는 코드만 추가하여 문제 해결할 수 있었다. 이전 문제 풀이와 기본적으로 같은 방법으로 풀기 때문에 이전 문제를 풀고 오는 것이 좋다.

https://ca.ramel.be/241

백준 11280번: 2-SAT - 3 (C++)

위 문제의 코드에서 추가된 것은 SCC 요소들을 저장하는 SCC라는 벡터를 추가한 것과, 이 벡터들의 요소들을 true/false 값으로 지정하는 것, 그리고 이를 출력하는 것이다.

코드

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

using namespace std;

#define endl '\n'
#define MAX_N 10001
#define MAX_M 100001

int N, M;
vector<int> Path[MAX_N * 2];
int id, sccNum;
int scc_id[MAX_N * 2];
int scc_finished[MAX_N * 2];
int sn[MAX_N * 2];
stack<int> scc_stack;
vector<vector<int>> SCC;
int ans[MAX_N];
int visited[MAX_N];

int Not(int a) {
    return (N < a ? a - N : a + N);
}

// SCC 알고리즘
int dfs(int c) {
    scc_id[c] = ++id;
    scc_stack.push(c);
    int res = scc_id[c];
    for (int next : Path[c]) {
        if (scc_id[next] == 0) {
            res = min(res, dfs(next));
        } else if (!scc_finished[next]) {
            res = min(res, scc_id[next]);
        }
    }
    if (res == scc_id[c]) {
        vector<int> scc;
        while (1) {
            int t = scc_stack.top();
            scc_stack.pop();
            scc.push_back(t);
            scc_finished[t] = 1;
            // 같은 SCC 끼리는 같은 숫자의 sn[x] 값을 갖게 된다.
            sn[t] = sccNum;
            if (t == c) break;
        }
        SCC.push_back(scc);
        sccNum++;
    }
    return res;
}

// 같은 SCC 에 x 와 ~x 가 동시에 있는지 체크하는 함수
int Check() {
    for (int i = 1; i <= N; i++) {
        if (sn[i] == sn[i + N]) return 0;
    }
    return 1;
}

// 변수들의 true/false 값을 저장하여 출력하는 함수
void PrintX() {
    for (vector<int> Temp : SCC) {
        for (int comp : Temp) {
            if (visited[comp <= N ? comp : Not(comp)]) continue;
            // comp 값이 N보다 크다면 그에 해당하는 순서의 변수를 false로, 그렇지 않다면 true 로 지정
            if (N < comp) {
                ans[Not(comp)] = 0;
                visited[Not(comp)] = 1;
            } else {
                ans[comp] = 1;
                visited[comp] = 1;
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        cout << ans[i] << ' ';
    }
    cout << endl;
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> N >> M;
    int a, b;
    for (int i = 0; i < M; i++) {
        cin >> a >> b;
        if (a < 0) a = -a + N;
        if (b < 0) b = -b + N;
        Path[Not(a)].push_back(b);
        Path[Not(b)].push_back(a);
    }
    for (int i = 1; i <= 2 * N; i++) {
        if (scc_id[i] == 0) dfs(i);
    }
    if (Check()) {
        cout << 1 << endl;
        PrintX();
    } else {
        cout << 0 << endl;
    }

    return 0;
}

더 생각해 볼 것?

문제를 풀었을 때, 예제에 대한 답이 일치하게 나오지 않아서 코드가 틀린 줄 알았는데, 스페셜 저지 문제에서는 한가지 문제에 대한 답이 여러개 나올 수 있다... 는걸 이번에 처음 알았다. 코드가 틀린줄 알고 뭔가 실수가 있나 오랜시간 고민했는데 그냥 제출하니 통과했다.. ㅠ

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!