백준 2224 - 명제 증명

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

 

주어지는 명제는 알파벳만 주어진다. 이때 알파벳을 아스키코드로 생각하면 명제의 범위를 대략 140 이내로 한정할 수 있으며 그렇게 되면 테이블이 dp[140][140]인 플로이드 워셜 알고리즘으로 해결할 수 있음을 알 수 있다.

 

주어진 입력을 인접 행렬로 표현해주고 플로이드 워셜을 수행한 후 전건과 후건이 연결된 것을 찾아 출력해주면 된다.

 

다만 a => a와 같이 자기와 같은 것은 친다고 하지 않으니 이를 유의하며 찾도록 한다.

 

전체 코드

#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2,fma")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
 
#include "bits/stdc++.h"
#include "ext/rope"
 
using namespace std;
using namespace __gnu_cxx;
 
using pii = pair<int, int>;
using ll = long long;
 
int dp[160][160];
 
void solve()
{
  int n;
  cin >> n;
  for (int i = 0; i < n; i++)
  {
    char go, to, trash;
    cin >> go >> trash >> trash >> to;
    dp[go][to] = 1;
  }
 
  for (int i = 1; i < 150; i++)
  {
    for (int j = 1; j < 150; j++)
    {
      for (int k = 1; k < 150; k++)
      {
        dp[j][k] |= (dp[j][i] and dp[i][k]);
      }
    }
  }
 
  int ans = 0;
 
  for (char i = 'A'; i <= 'z'; i++)
  {
    for (char j = 'A'; j <= 'z'; j++)
    {
      if (i == j) continue;
      if (dp[i][j]) ++ans;
    }
  }
  cout << ans << '\n';
 
  for (char i = 'A'; i <= 'z'; i++)
  {
    for (char j = 'A'; j <= 'z'; j++)
    {
      if (i == j) continue;
      if (dp[i][j]) cout << i << " => " << j << '\n';
    }
  }
}
 
int main()
{
  cin.tie(nullptr);
  ios::sync_with_stdio(false);
 
  solve();
}

제출 기록