백준 2224 명제 증명

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

bool g[58][58];





int main() {


    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n;
    int cnt = 0;
    cin >> n;
    cin.ignore();

    for (int i = 0; i < n; i++) {
        string s;

        getline(cin, s);

        if (s[0] == s[5] || g[s[0] - 'A'][s[5] - 'A']) {
            continue;
        }

        cnt++;
        g[s[0] - 'A'][s[5] - 'A'] = true;


    }

    for (int k = 0; k < 58; k++) {
        for (int i = 0; i < 58; i++) {
            for (int j = 0; j < 58; j++) {
                if (g[i][j] || i == j || k >= 26 && k <= 31 || i >= 26 && i <= 31 || j >= 26 && j <= 31) {
                    continue;
                }
                if(g[i][j] = g[i][k] && g[k][j]) {
                    cnt++;
                }

            }
        }
    }

    cout << cnt << '\n';
    for (int i = 0; i < 58; i++) {
        for (int j = 0; j < 58; j++) {
            if (g[i][j]) {
                cout << (char)(i + 'A') << " => " << (char)(j + 'A')<<'\n';
            }
        }
    }


    return 0;
}

 

 

All Pairs Shortest Path 문제이다.

그래프가 주어지고, 이 그래프에 대한 모든 가능한 쌍을 구하는 문제이다.

floyd 알고리즘을 사용하여 문제를 해결할 수 있다.

 

    for (int k = 0; k < 58; k++) {
        for (int i = 0; i < 58; i++) {
            for (int j = 0; j < 58; j++) {
                if (g[i][j] || i == j || k >= 26 && k <= 31 || i >= 26 && i <= 31 || j >= 26 && j <= 31) {
                    continue;
                }
                if(g[i][j] = g[i][k] && g[k][j]) {
                    cnt++;
                }

            }
        }
    }

 

'A'=65, 'z'=122이므로 58번 반복문을 돌린다. 그 과정에서 91~96은 알파벳이 아니므로 계산하지 않는다. 

i->j에서 k를 거쳐 가는 경로가 존재한다면 i->j도 존재한다는 점을 이용해 증명 가능한 명제를 구할 수 있다.

 

    cout << cnt << '\n';
    for (int i = 0; i < 58; i++) {
        for (int j = 0; j < 58; j++) {
            if (g[i][j]) {
                cout << (char)(i + 'A') << " => " << (char)(j + 'A')<<'\n';
            }
        }
    }

 

이후 명제의 개수와 해당 명제를 출력하면 답을 구할 수 있다.

 

    cin >> n;
    cin.ignore();

    for (int i = 0; i < n; i++) {
        string s;

        getline(cin, s);

        if (s[0] == s[5] || g[s[0] - 'A'][s[5] - 'A']) {
            continue;
        }

        cnt++;
        g[s[0] - 'A'][s[5] - 'A'] = true;


    }

 

입력은 해당 방법으로 받았는데, cin.ignore() 함수를 이용하면 cin>>n에서 남아있는 버퍼의 개행 문자를 비우고, getline(cin, s)를 통해 공백이 있는 문자를 입력받을 수 있다.