[ BOJ / C++ ] 15723번 : n단 논법

[ BOJ ] 15723번 : n단 논법

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

---

[  문제  ]

모든 중앙대 컴퓨터공학부(소프트웨어학부) 학생들은 미인이다.
지무근은 중앙대 컴퓨터공학부 학생이다.
그러므로 지무근은 미인이다.

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

[  입력  ]

첫째 줄에 정수 n(2 ≤ n ≤ 26)이 주어진다.

둘째 줄부터 n개의 줄에 걸쳐 각 줄에 전제가 하나씩 주어진다. 전제는 모두 a is b의 형식으로 주어지며 a와 b는 서로 다른 임의의 알파벳 소문자이다. 특별한 명시는 없지만 모든 전제는 “모든 a는 b이다”라는 의미이다. 하지만 “모든 b는 a이다”의 의미는 될 수 없다. 또한 a는 b이면서 c일 수 없으나, a와 b가 동시에 c일 수는 있다.

n + 2번째 줄에 정수 m(1 ≤ m ≤ 10)이 주어진다. 그 다음 m개의 줄에 걸쳐 각 줄에 하나의 결론이 전제와 같은 형식으로 주어진다.

[  출력  ]

m개의 줄에 걸쳐 각 줄에 결론이 참인지 거짓인지 출력하라. 참일 경우 T, 거짓일 경우 F를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다.

[  예제 입력 1  ]

3
a is b
b is c
c is d
3
a is d
a is c
d is a

[  예제 출력 1 ]

T
T
F

---

[  문제 접근 및 풀이  ]

n단 논법이 트리 구조와 비슷하다고 생각하여 Vector를 통하여 a가 b의 부모가 될 수 있게 만들었다.

참일 경우 a를 조상 노드로 삼아 BFS를 돌렸을 경우 후손 노드인 b를 만날 수 있어야 한다고 생각되었으며

만나지 않았을 경우에는 n단 논법에 위배되어 F를 출력하도록 하였다.

[  소스 코드  ]

#include<bits/stdc++.h>
using namespace std;
int n,m;
string is;
char a,b;
vector<int> ARG[27];
void Q_15662();
bool bfs();
int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	Q_15662();
}
void Q_15662(){
    cin >> n;
    for(int i=0;i<n;i++){
        cin >> a >> is >> b;
        ARG[(int)(a-'a')].push_back((int)(b-'a'));
    }
    cin >> m;
    for(int i=0;i<m;i++){
        cin >> a >> is >> b;
        if(bfs()) cout << "T\n";
        else cout << "F\n";
    }
}
bool bfs(){
    queue<int> veri;
    bool vis[27];
    memset(vis,0,sizeof(vis));
    veri.push((int)(a-'a'));
    vis[a-'a']=true;
    while(!veri.empty()){
        auto cur= veri.front(); veri.pop();
        for(auto x:ARG[cur]){
            if(vis[x]) continue;
            if(x==((int)(b-'a'))) return true;
            veri.push(x);
            vis[x]=true;
        }
    }
    return false;
}

---