백준 2224번 명제 증명 - C++ 풀이

---

 

1. 전건과 후건을 각각 그래프의 노드로 생각하고, 전건에서 후건으로 가는 간선을 추가한다.
2. 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면 P => Q를 증명할 수 있다. 
3. 플로이드와샬을 사용하여 모든 순서쌍 (p, q)에 대해 p에서 q로 가는 경로가 있는지 확인한다.

 

1. 전건과 후건을 각각 그래프의 노드로 생각하고, 전건에서 후건으로 가는 간선을 추가한다.

 주어지는 명제들의 전건과 후건을 각각 그래프의 노드라고 생각하자. 그리고 전건과 후건을 방향 간선(전건->후건)으로 잇는다. 

 

2. 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면 P => Q를 증명할 수 있다. 

 완성된 그래프에서 만약 정점 P에서 정점 Q로 가는 경로가 존재한다면, P => Q를 증명할 수 있다는 의미이다.

 

3. 플로이드와샬을 사용하여 모든 순서쌍 (p, q)에 대해 p에서 q로 가는 경로가 있는지 확인한다.

 증명가능한 모든 명제 P => Q를 구하는 것은, P->Q로 가는 경로가 존재하는 모든 노드 쌍 (P, Q)를 구하는 것과 같다. 따라서 모든 노드 순서쌍에 대해 경로가 존재하는지 여부를 알아야하므로, 플로이드와샬 알고리즘을 사용한다. 노드의 개수는 최대 52개(알파벳 대소문자)뿐이므로, O(N^3)으로도 충분하다.

---

#include <iostream>
#include <vector>

using namespace std;

const int INF = 987654321;

int N;
int dist[52][52];
vector<pii> ans;

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

char toChar(int x) {
    if (x < 26) return 'A' + x;
    else return 'a' + x - 26;
}

void floydWarshall() {
    for (int k=0; k<52; k++) {
        for (int i=0; i<52; i++) {
            for (int j=0; j<52; j++) {
                dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
            }
        }
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    string temp;
    int p, q;
    
    cin >> N;
    cin.ignore();
    for (int i=0; i<52; i++) {
        for (int j=0; j<52; j++) {
            dist[i][j] = INF;
        }
    }
    for (int i=0; i<N; i++) {
        getline(cin, temp);
        p = toInt(temp[0]);
        q = toInt(temp[5]);
        dist[p][q] = 1;
    }
    
    floydWarshall();
    
    for (int i=0; i<52; i++) {
        for (int j=0; j<52; j++) {
            if (dist[i][j] == INF || i == j) continue;
            ans.push_back({i, j});
        }
    }
    
    cout << ans.size() << "\n";
    for (auto prop: ans) {
        cout << toChar(prop.first) << " => " << toChar(prop.second) << "\n";
    }
    
    return 0;
}