[BOJ/Silver 1] 백준 15723 n단 논법(C++)

문제 링크

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

15723번: n단 논법

 

 

문제

모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.

지무근은 중앙대 컴퓨터공학부 학생이다.

그러므로 지무근은 미인이다.

 

위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, n개의 전제가 있을 때 m개의 결론을 도출할 수 있을 것이다. 이때의 n과 m은 모든 의미에서 적절한 수라고 가정하자. 자세한 것은 입출력 예시를 확인하자.

입력

첫째 줄에 정수 n(2 ≤ n ≤ 26)이 주어진다.

둘째 줄부터 n개의 줄에 걸쳐 각 줄에 전제가 하나씩 주어진다. 전제는 모두 a is b의 형식으로 주어지며 a와 b는 서로 다른 임의의 알파벳 소문자이다. 특별한 명시는 없지만 모든 전제는 “모든 a는 b이다”라는 의미이다. 하지만 “모든 b는 a이다”의 의미는 될 수 없다. 또한 a는 b이면서 c일 수 없으나, a와 b가 동시에 c일 수는 있다.

n + 2번째 줄에 정수 m(1 ≤ m ≤ 10)이 주어진다. 그 다음 m개의 줄에 걸쳐 각 줄에 하나의 결론이 전제와 같은 형식으로 주어진다.

출력

m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다.

예제 입력 1

3
a is b
b is c
c is d
3
a is d
a is c
d is a

예제 출력 1

T
T
F

알고리즘 분류

• 최단 거리 알고리즘

풀이

DP[26][26]이라는 2차원 배열을 선언한다.

DP[A][B]가 무한대(여기서는 10^9)라면 A이면 B이다. 가 거짓이라는 뜻이고 무한대가 아니라면 A이면 B이다. 가 참이라는 뜻이다.

N개의 전제를 입력받고 전제에 따라 DP[A][B]를 기록한다.

그 후 플로이드-워셜을 활용하여 문자 간의 상관관계를 모두 파악한다.

마지막으로 M개의 결론이 참인지 거짓인지 판별한다.

소문자 알파벳 26개만 주어지기 때문에 O(n^3)의 시간복잡도를 가져도 시간이 초과되지 않는다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 26
#define INF 1e9
#define FASTIO cin.tie(0); cout.tie(0); ios::sync_with_stdio(false);

using namespace std;
int N, M;
char A, B;
string IS;
int DP[MAX][MAX];

void init() {
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (i == j) {
                continue;
            }
            DP[i][j] = INF;
        }
    }
}

void settings() {
    for (int k = 0; k < MAX; k++) {
        for (int i = 0; i < MAX; i++) {
            for (int j = 0; j < MAX; j++) {
                if (i == j) {
                    continue;
                }
                if (DP[i][j] > DP[i][k] + DP[k][j]) {
                    DP[i][j] = DP[i][k] + DP[k][j];
                }
            }
        }
    }
}

void find_Answer() {
    if (DP[A - 'a'][B - 'a'] == INF) {
        cout << "F\n";
    }
    else {
        cout << "T\n";
    }
}

void input() {
    cin >> N;
    while (N--) {
        cin >> A >> IS >> B;
        int X = A - 'a';
        int Y = B - 'a';
        DP[X][Y] = 1;
    };
    settings();
    cin >> M;
    while (M--) {
        cin >> A >> IS >> B;
        find_Answer();
    };
}

int main() {
    FASTIO
    init();
    input();

    return 0;
}