[C++] 11280번 2-SAT - 3 - 그래프 이론, 강한 연결 요소, 2-sat

2-SAT - 3이랑 2-SAT - 4랑 한꺼번에 풀어서 함께 풀이해보려고 한다.

 

1. 문제

1. 변수의 개수 N과 절의 개수 M, 그리고 식 f가 주어졌을 때, 식 f를 true로 만들 수 있는지 없는지를 구하는 프로그램을 작성하라. (있으면 그 해를 출력하라 <2-SAT - 4>)
   • \(N(1 \leq N \leq 10,000)\), \(M(1 \leq M \leq, 100,000)\)
2. <입력>
   1. N과 M
   2. 절 \((1 \leq, \left|i \right|, \left|i \right| \leq N)\) i, j가 양수인 경우 xi, xj를 음수인 경우는 ㄱx-i, ㄱx-j를 나타낸다.
3. <출력
   1. 식 f를 true로 만들 수 있으면 1을, 없으면 0을 출력하라. (식 f가 true가 될 수 있을 경우 그 해를 출력하라. <2-SAT - 4>)

2. 문제 재정의

• 식에 true가 될 수 있는 xk가 있는지 판단하라. (있으면 그 해를 구하라 <2-SAT - 4>)

3. 해결 방법

1. a, b를 받자. xa -> 2*a-1, !xa -> 2*a으로 하고 !a -> b와 !b -> a를 그래프에 추가하자
   • ex) Vertex[2*a].push_back(2*b-1)
2. 그래프를 생성하고 나서 타잔 알고리즘을 이용해 강한 연결 요소 끼리 묶어보자.
3. 타잔 알고리즘으로 탐색한 강한 연결 요소 각각에 번호를 매겨주면 SCC_Count[n*2-1] == SCC_Count[n*2]를 통해 같으면 불가능, 다르면 가능하다는 것을 알 수 있다.
4. 가능할 경우 타잔의 탐색 순서로 노드를 정리해주자. 타잔의 역순으로 위상 정렬이 되기 때문에 a -> !a의 경우 !a가 참이되어야 하므로 위상 정렬의 역순으로 값을 설정해주어야 한다.
5. isTrue[i]에 값이 들어 있지 않은 경우 값/2에 !(값%2)를 넣어준다.

4. 실수한 점, 개선한 점

1. 나중에 isTrue값을 설정해줄 때 노드의 값을 2로 나눠주게 되면 2*a-1은 a-1로 2*a는 a로 값이 달라지므로 (노드의 값+1)을 2로 나눠주어야 한다.

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

#define FOR(i, k, N) for(int i=k; i<=N; i++)

using namespace std;

const int MAX_N = 10001;
const int MAX_M = 100001;

//변수의 개수 N, 절의 개수 M
int N, M;
//그래프
vector<int> Edge[MAX_M*2];
//타잔 알고리즘에서 방문한 순서, SCC로 묶인 순서, 타잔 알고리즘 탐색 순서
int visited[MAX_N*2], SCC_Count[MAX_N*2];
int visitCnt, SCC_CountTmp;
stack<int> st;
//각 Xk값 참, 거짓
bool isTrue[MAX_N];
//f(x)를 참으로 만드는 것이 가능한가?
bool isPossible;

//!x의 노드를 반환한다.
int reverse(int x)
{
    return (x&1) ? (x+1):(x-1);
}

void input()
{
    cin >> N >> M;
    
    FOR(i, 1, M) {
        int a, b;
        
        cin >> a >> b;
        //a가 참일 경우 2*a-1에, 거짓일 경우 2*a에 저장한다.
        a = (a > 0) ? (2*a-1):(-a*2);
        b = (b > 0) ? (2*b-1):(-b*2);
        
        //그래프 생성하기
        Edge[reverse(a)].push_back(b);
        Edge[reverse(b)].push_back(a);
    }
}

//타잔 알고리즘
int FindingSCC(int Node)
{
    st.push(Node);
    visited[Node] = ++visitCnt;
    
    int parent = visited[Node];
    
    FOR(i, 0, (int)Edge[Node].size()-1) {
        int next = Edge[Node][i];
        if(!visited[next])
            parent = min(parent, FindingSCC(next));
        else if(!SCC_Count[next])
            parent = min(parent, visited[next]);
    }
    
    if(parent == visited[Node]) {
        ++SCC_CountTmp;
        while(1) {
            int here = st.top(); st.pop();
            SCC_Count[here] = SCC_CountTmp;
            if(here == Node)
                break;
        }
    }
    
    return parent;
}

void solve()
{
    //아직 SCC로 묶이지 않았을 경우 SCC로 묶어주기
    FOR(i, 1, N*2)
        if(!SCC_Count[i])
            FindingSCC(i);
    
    isPossible = true;
    for(int i=1; i<=N*2-1; i+=2)
        //같은 SCC로 묶였으므로 불가능
        if(SCC_Count[i] == SCC_Count[i+1])
            isPossible = false;
    
    cout << isPossible;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    
    input();
    
    //2-SAT-문제 해결하기
    solve();
    
    return 0;
}

 

 

※현재 고등학교 등교 중인 학생입니다. 이제 알고리즘을 본격적으로 공부하기 시작해서 아직 초보입니다. 혹시 제가 잘못 알고 있는 점이나 더 좋은 풀이 방법이 있어 댓글에 남겨주시면 감사히 하나하나 열심히 읽어보겠습니다. 좋아요, 단순한 댓글 한마디라도 저에겐 큰 힘이 됩니다! 감사합니다.