[C/C++] 백준 - 15723번 : n단 논법

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

15723번: n단 논법

문제

모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.

지무근은 중앙대 컴퓨터공학부 학생이다.

그러므로 지무근은 미인이다.

위 연역 논증은 대표적인 삼단논법의 예시이다. 삼단논법이란 전제 두 개와 결론 하나로 이루어진 연역 논증이다. 이것을 응용하면, n개의 전제가 있을 때 m개의 결론을 도출할 수 있을 것이다. 이때의 n과 m은 모든 의미에서 적절한 수라고 가정하자. 자세한 것은 입출력 예시를 확인하자.

---

이 문제와 같은 유형을 최근에 푼 적이 있다.

n단 논법 문제는 결국 모두 그래프 형태로 볼 수 있다. 방향성이 있는 그래프 문제로 해결가능하다.

 

이 문제 또한 _ is _ 라는 정해진 형식으로 _에는 알파벳 'a' ~ 'z'가 올 수 있다. 

즉, 전체 노드의 개수가 26개 밖에 되지 않는 매우 간단한 문제로 볼 수 있다.

 

그리고 정해진 형식으로 _ is _가 오기 때문에 결국 플로이드-와샬 문제로 해결 가능한 형태가 될 것이다.

나는 BFS 형태로 문제를 해결하였다.

 

Step 1.

_ is _라는 형식에서 첫 번째 _에서 두 번째 _로 이어나갈 수 있다는 것을 의미하기 때문에 -> 방향을 가진 형태로 이어준다.

 

Step 2.

_ is _라는 형식에서 첫 번째 _에서 너비 우선 탐색을 통해 두 번째 _까지 도달할 수 있는지 확인해준다. 만약 도달할 수 있다는 것은 주어진 결론이 참이라는 것을 의미하므로 T를 출력해준다.

 

 

#include <bits/stdc++.h>
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

int N;
bool visited[26 + 1];
vector<int> adj[26 + 1];

void input(){
    cin >> N;
    cin.ignore();

    for(int i=0;i<N;i++){
        string info; 
        getline(cin, info);

        adj[info[0] - 'a' + 1].push_back(info[5] - 'a' + 1);
    }
}

bool isValid(int node1, int node2){
    queue<int> q;
    q.push(node1);
    
    memset(visited, false, sizeof(visited));
    visited[node1] = true;

    while(!q.empty()){
        int y = q.front();
        q.pop();

        if(y == node2) return true;

        for(auto &t : adj[y]){
            if(!visited[t]){
                visited[t] = true;
                q.push(t);
            }
        }
    }
    return false;
}

void solution(){
    int M; cin >> M;
    cin.ignore();

    for(int i=0;i<M;i++){
        string info;
        getline(cin, info);

        if(isValid(info[0] - 'a'  + 1, info[5] - 'a' + 1)) cout << "T" << endl;
        else cout << "F" << endl;
    }
}

int main(){
    fastio;
    input();
    solution();

    return 0;
}