[boj]15723 - n단논법(Floyd Warshall, string 입출력)

www.acmicpc.net/problem/15723

15723번: n단 논법

- 플로이드 와샬 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제이다.

- 플로이드 와샬을 통해서 입력을 통해 주어진 논증 외에도 2~n단 논법을 통해서 징검다리 식으로 증명할 수 있는 논증에 대해서 

차례차례 DP 스타일로 증명해 나갈 수 있다. 

- string 전체를 입력으로 받을 때 getline(cin, string)을 쓰는데 이전에 cin으로 입력을 받았다면 꼭 flushing을 해서 버퍼에 남아있는 '\n'을 제거 해줘야한다. 

#include <iostream>
#include <string>
using namespace std;

const int MAX = 26;
int n;             // 2~26
bool a[MAX][MAX];  // i -> j 증명

// 플로이드와샬로 i->j 사이의 중간 논증을 증명해준다.(i->k->j)

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

    cin >> n;
    cin.ignore();  // cin과 getline 같이 쓸 때 '\n' 꼭 플러싱 해주기

    for (int i = 0; i < MAX; ++i) {
        for (int j = 0; j < MAX; ++j) {
            if (i == j)
                a[i][j] = true;
            else
                a[i][j] = false;
        }
    }  // i==j이면 무조건 옳은 논증

    for (int i = 0; i < n; ++i) {
        string s;
        getline(cin, s);
        int from = s.front() - 'a';
        int to = s.back() - 'a';
        a[from][to] = true;
    }

    for (int k = 0; k < MAX; ++k) {
        for (int i = 0; i < MAX; ++i) {
            for (int j = 0; j < MAX; ++j) {
                if (a[i][k] && a[k][j]) {  // 플로이드로 i->k->j 증명 추가
                    a[i][j] = true;
                }
            }
        }
    }

    int m;
    cin >> m;
    cin.ignore();
    while (m--) {
        string s;
        getline(cin, s);
        int from = s.front() - 'a';
        int to = s.back() - 'a';

        if (a[from][to]) {
            cout << 'T' << '\n';
        } else {
            cout << 'F' << '\n';
        }
    }

    return 0;
}