BOJ 12601 - Polygraph (Small) 링크
(2024.03.11 기준 G4)

문제

$N$명의 사람들은 진실만을 말하는 Truthtown이나, 거짓만을 말하는 Liarville에서 왔다.

• $i$ $T$ $j$ : $i$번 사람이 "$j$번 사람은 Truthtown에서 왔다."라고 말했다.
• $i$ $L$ $j$ : $i$번 사람이 "$j$번 사람은 Liarville에서 왔다."라고 말했다.
• $i$ $S$ $j$ $k$ : $i$번 사람이 "$j$번 사람과 $k$번 사람은 같은 도시에서 왔다."라고 말했다.
• $i$ $L$ $j$ $k$ : $i$번 사람이 "$j$번 사람과 $k$번 사람은 다른 도시에서 왔다."라고 말했다.
  $M$개의 상태가 주어질 때, 각 사람의 출신 도시를 판단해서 출력

알고리즘

간단하진 않은 브루트포스

풀이

$N$의 제한이 최대 $10$밖에 되지 않는다. 그리고 도시는 총 $2$개이다. 그래서 일단 각 사람에 대해 도시를 정해놓고 상태가 유효한지에 검사하는 $O(T2^NM)$의 시간복잡도를 갖는 브루트포스 방법이 통함을 알 수 있다.

위를 이해했으면 바로 어떻게 할지 떠오를텐데, 하나 막힐 수 있는 부분이 있다. 바로 -를 출력해야 함을 판단하는 부분.

경우의 수마다 주어진 모든 상태가 유효하면 그때의 경우의 수를 체크를 할 것인데, 이때 정확하게 하나의 경우의 수만 모든 상태가 유효함을 만족하지 않을 수 있다. 그러므로 만약 $i$번 사람이 두 도시 모두 가능하다면 -를 출력하면 된다. 밑에 코드를 보면 바로 이해를 할 수 있을 것이다.

코드

• C++

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

const int MAXN = 10;

struct s1{
    int i, c, j;
};

struct s2{
    int i, c, j, k;
};

int N, M, res[MAXN];
bool ans[MAXN][2];
vector<s1> S1;
vector<s2> S2;

void dfs(int n){
    if (n == N){
        // 한 사람에 대한 상태를 체크
        for (auto [i, c, j]: S1){
            if (res[i]){ // i가 1이면 진실을 말한다.
                if (res[j] != c) return;
            }
            else{ // i가 0이면 거짓을 말한다.
                if (res[j] == c) return;
            }
        }
        // 두 사람에 대한 상태를 체크
        for (auto [i, c, j, k]: S2){
            if (res[i]){ // i가 1이면 진실을 말한다.
                if (c){
                    if (res[j] != res[k]) return;
                }
                else{
                    if (res[j] == res[k]) return;
                }
            }
            else{ // i가 0이면 거짓을 말한다.
                if (c){
                    if (res[j] == res[k]) return;
                }
                else{
                    if (res[j] != res[k]) return;
                }
            }
        }
        // 모든 상태가 유효하다면, 현재 경우의 수를 이루는 도시를 체크
        for (int i = 0; i < N; i++) ans[i][res[i]] = true;
        return;
    }

    dfs(n + 1);
    res[n] = 1;
    dfs(n + 1);
    res[n] = 0;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);

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

        S1.clear(); // 한 사람에 대한 상태
        S2.clear(); // 두 사람에 대한 상태
        int i, j, k; char c;
        while (M--){
            cin >> i >> c >> j;
            if (c == 'T') S1.push_back({--i, 1, --j});
            else if (c == 'L') S1.push_back({--i, 0, --j});
            else{
                cin >> k;
                if (c == 'S') S2.push_back({--i, 1, --j, --k});
                else S2.push_back({--i, 0, --j, --k});
            }
        }

        // 도시는 2개 뿐이라서 모든 경우의 수에 대해 체크할 수 있다.
        // 경우의 수마다, 주어진 모든 상태가 유효하다면 가능한 도시를 체크
        fill(&ans[0][0], &ans[N - 1][2], false);
        fill(res, res + N, 0); // 0: Liarville, 1: Truthtown
        dfs(0);

        cout << "Case #" << x << ":";
        for (int i = 0; i < N; i++){
            if (ans[i][0]){
                if (ans[i][1]) cout << " -"; // 둘 다 가능하다면 정확하게 도시를 판별할 수 없다.
                else cout << " L";
            }
            else cout << " T"; // 둘 다 가능하지 않은 경우는 주어지지 않는다.
        }
        cout << '\n';
    }
}

• Python

import sys; input = sys.stdin.readline

def dfs(n):
    if n == N:
        # 한 사람에 대한 상태를 체크
        for i, c, j in S1:
            if res[i]: # i가 1이면 진실을 말한다.
                if res[j] != c:
                    return
            else: # i가 0이면 거짓을 말한다.
                if res[j] == c:
                    return
        # 두 사람에 대한 상태를 체크
        for i, c, j, k in S2:
            if res[i]: # i가 1이면 진실을 말한다.
                if c:
                    if res[j] != res[k]:
                        return
                else:
                    if res[j] == res[k]:
                        return
            else: # i가 0이면 거짓을 말한다.
                if c:
                    if res[j] == res[k]:
                        return
                else:
                    if res[j] != res[k]:
                        return
        # 모든 상태가 유효하다면, 현재 경우의 수를 이루는 도시를 체크
        for i in range(N):
            ans[i][res[i]] = True
        return

    dfs(n + 1)
    res[n] = 1
    dfs(n + 1)
    res[n] = 0

for x in range(1, int(input()) + 1):
    N, M = map(int, input().split())

    S1 = [] # 한 사람에 대한 상태
    S2 = [] # 두 사람에 대한 상태
    for _ in range(M):
        s = input().split()
        if len(s) == 3:
            i = int(s[0]) - 1; j = int(s[2]) - 1
            if s[1] == 'T':
                S1.append((i, 1, j))
            else:
                S1.append((i, 0, j))
        else:
            i = int(s[0]) - 1; j = int(s[2]) - 1; k = int(s[3]) - 1
            if s[1] == 'S':
                S2.append((i, 1, j, k))
            else:
                S2.append((i, 0, j, k))

    # 도시는 2개 뿐이라서 모든 경우의 수에 대해 체크할 수 있다.
    # 경우의 수마다, 주어진 모든 상태가 유효하다면 가능한 도시를 체크
    ans = [[False] * 2 for _ in range(N)]
    res = [0] * N # 0: Liarville, 1: Truthtown
    dfs(0)

    print('Case #%d:' % x, end = '')
    for i in range(N):
        if ans[i][0]:
            if ans[i][1]: # 둘 다 가능하다면 정확하게 도시를 판별할 수 없다.
                print(' -', end = '')
            else:
                print(' L', end = '')
        else: # 둘 다 가능하지 않은 경우는 주어지지 않는다.
            print(' T', end = '')
    print()