[알고리즘] 백준 2224번: 명제 증명 (C++)

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

2224번: 명제 증명

이번 문제는 2가지 포인트를 얻어낼 수 있었다.

 

1. 플로이드 와샬이다보니 일반적인 그래프처럼 하나의 명제의 가중치를 1로 두고 풀어서 삼단논법에 의해 2,3,... 이 되는 경우들에 의해 헷갈렸었는데 bool 타입을 이용한 플로이드 와샬로 간단하게 볼 수 있었다.

 

2. 명제의 개수를 셀 때, 반례를 찾아서 오류를 알아낼 수 있었다.

3
a => b
b => c
c => a

이러한 input일 때, 개수가 7이 나왔었는데 6이 나왔어야 했다. 그래서 더 간결하게 플로이드 와샬을 모두 끝낸 후, cnt를 해주었다.

(주석된 부분이 틀린 cnt 방식이다.)

 

[AC 코드]

#include <iostream>
#define MAX_V ('z'-'A'+1)
using namespace std;

// 간단하게 생각할 수 있는 건 간단하게
bool map[MAX_V + 1][MAX_V + 1];
int n;
int cnt = 0;

void floydWarshall(){
    for(int k = 1; k <= MAX_V; k++){
        for(int i = 1; i <= MAX_V; i++){
            for(int j = 1; j <= MAX_V; j++){
                if(map[i][k] && map[k][j]){
                    if(i == j) continue;
                    map[i][j] = true;
                    //cnt++;
                }
            }
        }
    }
}

int main(){
    cin >> n;
    cin.ignore();
    
    for(int i = 0; i < n; i++){
        string s;
        getline(cin, s, '\n');
        char a = s[0];
        char b = s[s.length() - 1];
        if(a == b) continue;
        //cnt++;
        map[a - 'A' + 1][b - 'A' + 1] = true;
    }
    
    floydWarshall();
    
    for(int i = 1; i <= MAX_V; i++){
        for(int j = 1; j <= MAX_V; j++){
            if(map[i][j]) cnt++;
        }
    }
    
    cout << cnt << '\n';
    for(int i = 1; i <= MAX_V; i++){
        for(int j = 1; j <= MAX_V; j++){
            if(map[i][j]){
                cout << (char)(i + 'A' - 1) << " => " << (char)(j + 'A' - 1) << '\n';
            }
        }
    }
    
    return 0;
}