[BOJ] 2224. 명제 증명 (C++)

문제

생각할 것

• 문제에서 알파벳에서 알파벳으로 가능한 경로를 구하라고 했으므로 플로이드 워셜을 쓰자
• 아스키코드 표를 확인해보니 대문자와 소문자 사이에 다른 문자들이 더 있었다..!!
• 알파벳 숫자가 26개여서 배열을 26 *2로 만들어 주었다가 out of bound에러가 발생했다.
  • 아스키코드 표를 확인해보니 대문자와 소문자 사이에 다른 문자들이 더 있었다..!!

  • 

• 전건과 후건이 같은 경우는 출력하지 않기로 한다는 조건을 추가하지 않았었다.
• 개수를 출력하지 않았었다……

코드

#include <iostream>
#include <vector>
#include <string>

#define INF 1e9
using namespace std;

int main() {
    int N;
    cin >> N;

    char A, B;
    string IS;
    int alphabetSize = 'z' - 'A' + 1;
    vector<vector<int>> adj(alphabetSize, vector<int>(alphabetSize, INF));
    for (int i = 0; i < N; i++) {
        cin >> A >> IS >> B;
        adj[A - 'A'][B - 'A'] = 1;
    }

    for (int k = 0; k < alphabetSize; k++) {
        for (int i = 0; i < alphabetSize; i++) {
            for (int j = 0; j < alphabetSize; j++) {
                if (adj[i][j] > adj[i][k] + adj[k][j]) {
                    adj[i][j] = adj[i][k] + adj[k][j];
                }
            }
        }
    }

    vector<pair<int, int>> res;
    for (int i = 0; i < alphabetSize; i++) {
        for (int j = 0; j < alphabetSize; j++) {
            if (i == j) continue;
            if (adj[i][j] != INF) res.push_back({i, j});
        }
    }

    cout << res.size() << endl;
    for (int i = 0; i < res.size(); i++) {
        cout << char(res[i].first + 'A') << " => " << char(res[i].second + 'A') << endl;
    }

    return 0;
}