백준 알고리즘 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를 출력하라. 알 수 없는 경우도 거짓이다. 답은 필히 대문자로 출력해야 한다.

예제 입력 및 출력

풀이법

간단한게 생각해서 A->B로 가는 경로가 INF가 아니라면 T, INF라면 F를 출력해주면 된다. :)

풀이 코드(C++)

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<deque>
#include<stack>
#include<string>
#include<list>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<bitset>
#include<tuple>
#include<functional>
#include<utility>
#include<cmath>
#include<cstdlib>
#include<cstring>
#include<complex>
#include<cassert>
#define X first
#define Y second
#define pb push_back
#define MAX 27
#define INF 1000000000
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
using namespace std;
using ll = long long;
using ull = unsigned long long;
using dbl = double;
using ldb = long double;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
using vi = vector<int>;

int dist[MAX][MAX];

void resetGraph(){
  for(int i = 0; i < MAX; i++){
    for(int j = 0; j < MAX; j++){
      dist[i][j] = INF;
    }
  }
}

void floyd(){
  for(int k = 0; k < MAX; k++){ // k : 거쳐가는 정점
      for(int i = 0; i < MAX; i++){ // i : 행(출발 정점)
        for(int j = 0; j < MAX; j++){ // j : 열(도착 정점)
         // 점화식 distance[i,j] = min(distance[i,j], distance[i,n] + distance[n,j])
          dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
        }
    }
  }
}

int n,m;

int main(){
  fastio;
  cin >> n;
  resetGraph();
  char a,b;
  string s;
  for(int i = 0; i < n; i++){
    cin >> a >> s >> b;
    dist[a - 'a'][b - 'a'] = 1;
  }
  cin >> m;
  floyd();
  while(m--){
    char x,y;
    string s;
    cin >> x >> s >> y;
    cout << (dist[x - 'a'][y - 'a'] == INF ? 'F' : 'T') << "\n"; 
  }
  return 0;
}