백준 5782 - This Sentence is False

 

 

문제 링크: https://acmicpc.net/problem/5782 

5782번: This Sentence is False

---

문제를 요약해봅시다.

• 주어진 $N$개의 문장은 각각 다른 문장 $X$의 참, 거짓 여부를 가리킵니다.
• 문장의 참, 거짓 여부를 조사하여 만약 모순이면 Inconsistent를, 모순이 아니면 참이 될 수 있는 문장의 최대 개수를 출력합니다.

---

- 사실 관계 유추

어떤 문장 $X$의 내용이 "문장 $Y$는 참이다" 라고 합시다. 이때 유추할 수 있는 사실은 다음의 2가지입니다.

• 문장 $X$가 참이면, 문장 $Y$도 참입니다.
• 문장 $X$가 거짓이면, 문장 $Y$도 거짓입니다.

 

이때 이 두 명제의 역도 성립합니다. 왜냐하면, 문장 $Y$가 참이면 문장 $X$가 참을 말하고 있는 것이기 때문입니다! 문장 $Y$가 거짓인 경우도 비슷합니다.

이와 유사하게, 문장 $X$의 내용이 "문장 $Y$는 거짓이다" 인 경우도 생각해 볼 수 있습니다. 이때 유추할 수 있는 사실은,

• 문장 $X$가 참이면, 문장 $Y$는 거짓입니다.
• 문장 $X$가 거짓이면, 문장 $Y$는 참입니다.

이 두 명제의 역도 역시나 성립합니다.

 

- 문제 구성 (그래프)

이러한 문장 간의 사실 관계를 나타낼만한 좋은 자료구조가 없을까요? 바로 그래프입니다.

그래프를 이용해서 문장 간의 관계를 표현해봅시다.

• 문장 $X$가 참인 경우와 거짓인 경우를 각각 정점 $x$, $\neg x$로 쓰겠습니다.
• 문장 $X$의 내용이 "문장 $Y$는 참이다" 이면, 두 정점 $x, y$를 잇는 양방향 간선과 두 정점 $\neg x, \neg y$를 잇는 양방향 간선을 추가합니다.
• 문장 $X$의 내용이 "문장 $Y$는 거짓이다" 이면, 두 정점 $x, \neg y$를 잇는 양방향 간선과 두 정점 $\neg x, y$를 잇는 양방향 간선을 추가합니다.

 

이때 양방향 간선을 쓰는 이유는, 각 문장이 만드는 2가지 명제가 그 역 또한 성립하는 명제들이기 때문입니다.

 

- 그래프 탐색

그래프를 구성했으니 이제 그래프를 탐색하면서 문장 간의 모순을 발견하거나 답을 구해봅시다. 탐색은 아무 방법이나 괜찮다고 생각하지만 이 글에서는 DFS를 사용하겠습니다.

 

간선으로 이어진 두 정점은 둘 다 참이거나 둘 다 거짓입니다. 즉 같은 그룹에 속한다고 볼 수 있습니다. 여기서 모순을 발견하려면 그래프를 탐색하다가, $x$와 $\neg x$가 같은 그룹에 속하는지를 찾아주면 됩니다. $x$와 $\neg x$는 절대로 같은 그룹에 속할 수 없기 때문입니다.

이걸 효과적으로 해결하려면 각 정점을 2가지 색으로 칠하면 됩니다. DFS로 방문하는 정점들의 색을 전부 색 1로 칠하고, 방문한 정점의 역에 해당하는 정점을 색 2로 칠해줍시다. 만약 탐색 중에 색 2인 정점을 탐색해야 된다면 모순이라는 것을 알 수 있습니다.

 

모순이 없다면 탐색한 정점들 중 문장이 참이 되게 하는 정점, 즉 $\neg$ 가 붙지 않은 정점 중 색 1로 칠해진 것의 개수를 세면 참이 되는 문장의 개수를 구할 수 있습니다.

그런데 색 2로 칠해진 문장이 더 많다면 어떻게 해야 할까요? 이때는 그냥 색 1과 색 2를 바꾸면 결과가 똑같기 때문에, 그냥 둘 중에 더 많은 것을 쓰면 됩니다.

 

여기서 주의해야 할 점은, 그래프가 연결 그래프면 좋겠지만 연결 그래프가 아닐 수 있다는 것입니다. 따라서 그래프의 모든 연결 요소를 다 처리할 때 까지 DFS를 잊지 말고 돌려주도록 합시다!

 

시간 복잡도는,

• DFS를 모든 정점에 대해 실행하고, 정점의 수가 $2N$, 간선의 수가 $2N$이므로 $O(2N + 2N) = O(N)$

따라서 총 $O(N)$입니다.

 

공간 복잡도는,

• 정점 $2N$개와 간선 $2N$개를 저장하므로 $O(2N + 2N) = O(N)$

따라서 총 $O(N)$입니다.

---

소스코드 (C++)

#include <bits/stdc++.h>

#define fastio ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

using namespace std;
typedef long long ll;
typedef __int128 xll;

// 매 탐색마다 방문한 문장의 수
int group = 0;
// 매 탐색마다 방문한 문장 중, 문장을 참으로 만들면서 색 1로 칠해진 문장의 수
int colored = 0;

// DFS를 하는 함수입니다. 모순이면 true를, 그 외에는 false를 반환합니다.
bool dfs(vector<int> &truth, vector<vector<int>> &edges, int n, int v) {
    // 방문 중인 정점을 색 1로 칠합니다.
    truth[v] = 1;
    group++;
    
    // 현재 문장의 역에 해당하는 정점은 색 2로 칠합니다. 
    if (v > n) truth[v - n] = 2;
    else {
    	// 방문 중인 정점이 문장이 참이 되는 경우라면 개수를 세줍니다.
        colored++;
        truth[v + n] = 2;
    }
    
    bool result = false;
    for (int c: edges[v]) {
        if (truth[c] == 0) {
        	// 만약 이웃한 정점이 방문하기 전이라면, 탐색을 시도합니다.
            result = result || dfs(truth, edges, n, c);
        }
        else if (truth[c] == 2) {
            // 만약 이웃한 정점의 색이 색 2라면 모순입니다.
            return true;
        }
    }
    
    return result;
}

int main() {
    fastio;
    
    string ts = "true.";
    string fs = "false.";
    
    while (1) {
        int n;
        cin >> n;
        
        if (n == 0) break;
        
        vector<int> truth(2 * n + 1);
        vector<vector<int>> edges(2 * n + 1);
        
        for (int i = 1; i <= n; i++) {
            string sen;
            int j;
            
            cin >> sen >> j >> sen >> sen;
            
            // 문장 간의 사실 관계를 나타내는 그래프를 구축합니다.
            if (sen == ts) {
                edges[i].push_back(j);
                edges[j].push_back(i);
                edges[i + n].push_back(j + n);
                edges[j + n].push_back(i + n);
            }
            else {
                edges[i].push_back(j + n);
                edges[j].push_back(i + n);
                edges[i + n].push_back(j);
                edges[j + n].push_back(i);
            }
        }
        
        bool incons = false;
        int cnt = 0;
        for (int i = 1; i <= n && !incons; i++) {
        	// 아직 탐색하지 않은 문장이 있다면 DFS로 탐색하며 정점의 색을 칠합니다.
            if (truth[i] == 0) {
                // 각 탐색마다 탐색한 문장의 수, 참 문장의 수를 구합니다.
                group = 0;
                colored = 0;
                
                // 탐색을 시도합니다.
                if (dfs(truth, edges, n, i)) incons = true;
                else {
                    // 탐색이 성공적이라면 참이 될 수 있는 문장의 수를 더해줍니다.
                    cnt += max(colored, group - colored);
                }
            }
        }
        
        if (incons) {
            cout << "Inconsistent\n";
            continue;
        }
        
        cout << cnt << "\n";
    }
}