[BOJ/Gold 4] 백준 2224 명제 증명(C++)

문제 링크

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

2224번: 명제 증명

 

 

문제

수학, 혹은 논리학에서 만약 무엇 이라면 뭣 일 것이다 하는 식의 명제가 널리 쓰인다. 예를 들어 "P이면 Q일 것이다." 라는 명제는 “P => Q” 라는 기호로 표현된다. 이때의 P를 전건, Q를 후건이라고 한다.

논리학에서 어떤 명제를 증명할 때 가장 널리 쓰이는 방법 중 한 가지가 바로 삼단 논법이다. 만약 두 명제 “P => Q", "Q => R" 가 모두 참이면, 명제 "P => R"이 역시 참이 된다. 이러한 방법을 사용했을 때 명제 ”P => R"이 증명되었다고 한다.

어떤 참인 명제가 주어졌을 때, 이 명제가 참이므로 이 명제 자체도 증명될 수 있다고 할 수 있다. 하지만 “P => P”와 같은 명제는 항상 참이 되는데, 이런 식으로 전건과 후건이 같은 경우는 출력하지 않기로 한다.

N개의 참인 명제들이 주어졌을 때, 증명될 수 있는 명제를 모두 구해내는 프로그램을 작성하시오. 명제를 증명하는 방법은 여러 가지가 있을 수 있지만, 위에서 언급한 방법만을 사용하기로 한다.

입력

첫째 줄에 정수 N(1 ≤ N ≤ 10,000)이 주어진다. 다음 N개의 줄에는 참인 명제들이 주어진다. 명제는 "P => Q"의 꼴로 주어지는데, “=>”는 앞뒤가 공백으로 구분되어 있다. P나 Q는 명제를 나타내는 문자인데, 알파벳 대소문자 한 글자를 사용한다. 같은 명제가 여러 번 주어질 수도 있다.

출력

첫째 줄에 출력할 명제의 개수 X개를 출력한다. 다음 X개의 줄에 증명될 수 있는 명제를 한 줄에 하나씩 출력한다. 명제를 출력할 때에는 전건 순으로 정렬하고, 전건이 같은 경우에는 후건 순으로 정렬한다. 알파벳은 대문자가 소문자에 우선한다. 즉, 정렬했을 때 A, B, …, Z, a, b, …, z 순서로 나와야 한다.

예제 입력 1

2
A => b
b => C

예제 출력 1

3
A => C
A => b
b => C

알고리즘 분류

• 최단 거리 알고리즘

풀이

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

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

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

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

소문자 알파벳 26개, 대문자 알파벳 26개만 주어지며, A는 65고 z는 122이기 때문에 A를 0이라고 한다면 z는 57이므로 범위는 0에서 57까지가 된다. 따라서 O(n^3)의 시간복잡도를 가져도 시간이 초과되지 않는다.

그리고 이중 for문을 사용해서 DP[A][B]가 무한대인지 아닌지를 판별하고, 무한대가 아니라면 A => B를 문자열로 벡터에 저장한다.

역시 O(n^2)의 시간복잡도를 가져도 시간이 초과되지 않는다.

0에서부터 시작해서 57까지 탐색하기 때문에 대문자 A부터 탐색하는 것이다. 따라서 정렬을 해줄 필요는 없다.

마지막으로 벡터의 크기를 int형으로 출력하고 벡터에 저장되어 있는 문자열들을 한 줄에 하나씩 출력한다.

코드

#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#define MAX 58
#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];
vector<string> X;

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 input() {
    cin >> N;
    while (N--) {
        cin >> A >> IS >> B;
        int X = A - 'A';
        int Y = B - 'A';
        DP[X][Y] = 1;
    };
}

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];
                }
            }
        }
    }
    for (int i = 0; i < MAX; i++) {
        for (int j = 0; j < MAX; j++) {
            if (i == j) {
                continue;
            }
            if (DP[i][j] != INF) {
                char First = (char)(i + 65);
                char Second = (char)(j + 65);
                string Tmp = "";
                Tmp += First;
                Tmp += " => ";
                Tmp += Second;
                X.push_back(Tmp);
            }
        }
    }
}

void find_Answer() {
    cout << X.size() << "\n";
    for (int i = 0; i < X.size(); i++) {
        cout << X[i] << "\n";
    }
}

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

    return 0;
}