[BOJ] 2224 - 명제 증명

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

BOJ - 명제 증명

문제 유형: 플로이드-워셜, 문자열 처리

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 128MB

 

문제

수학, 혹은 논리학에서 만약 무엇 이라면 뭣 일 것이다 하는 식의 명제가 널리 쓰인다. 예를 들어 "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 순서로 나와야 한다.

 

풀이

아스키를 받아서 숫자로 바꾸거나, 숫자를 아스키로 바꿀 때 주의를 잘 해줘야 한다.

플로이드 워셜로 갈 수 있는지에 대한 행렬을 완성하고 순서대로 출력해주면 된다.

 

코드

C++

#include <bits/stdc++.h>

using namespace std;

int myAtoi(char c) {
    if (c >= 'A' && c <= 'Z') {
        return c - 'A';
    } else {
        return c - 'a' + 26;
    }
}

string myItoa(int x) {
    char res;
    if (x < 26) {
        res = 'A' + x;
    } else {
        res = 'a' + x - 26;
    }
    return string(1, res);
}

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n;
    cin >> n;

    vector<vector<bool>> adj(52, vector<bool>(52, false));

    for (int i = 0; i < n; ++i) {
        char p, q;
        string arrow;
        cin >> p >> arrow >> q;

        int a = myAtoi(p);
        int b = myAtoi(q);

        adj[a][b] = true;
    }

    for (int k = 0; k < 52; k++) {
        for (int i = 0; i < 52; i++) {
            for (int j = 0; j < 52; j++) {
                adj[i][j] = adj[i][j] || (adj[i][k] && adj[k][j]);
            }
        }
    }

    string ans;
    int cnt = 0;
    for (int i = 0; i < 52; i++) {
        for (int j = 0; j < 52; j++) {
            if (i != j && adj[i][j]) {
                cnt++;
                ans += myItoa(i) + " => " + myItoa(j) + "\n";
            }
        }
    }

    cout << cnt << "\n";
    cout << ans;

    return 0;
}