[백준 / BOJ] C++ 1613 역사

1613번: 역사

 

문제

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

1613번: 역사

 

 

풀이

여러 사건의 선후 관계를 판단하는 문제다. 플로이드-워셜 알고리즘을 사용해 풀 수 있다. a가 b보다 먼저 일어났다고 할 때 dist[a][b] = 1, 나머지는 INF로 플로이드를 돌린다. 그리고 x, y의 선후 관계를 알고 싶을 때, dist[x][y]가 INF가 아니라면 x가 먼저 일어난 일이고(-1 출력), INF면 x가 먼저 일어난 일은 아니다. 이때 dist[y][x]가 INF가 아니면 y가 먼저 일어난 일이고(1 출력), INF면 어떤지 모르는(유추할 수 없는, 0 출력) 상황이다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int N, K, dist[401][401], S;
  cin >> N >> K;
  // dist 배열 초기화
  for (int i = 1; i <= N; i++)
    for (int j = 1; j <= N; j++)
      dist[i][j] = i == j ? 1 : INF;
  // 간선 입력
  while (K--) {
    int a, b;
    cin >> a >> b;
    dist[a][b] = 1;
  }
  // 플로이드 워셜
  for (int k = 1; k <= N; k++)
    for (int i = 1; i <= N; i++)
      for (int j = 1; j <= N; j++)
        dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
  // 출력
  cin >> S;
  while (S--) {
    int a, b;
    cin >> a >> b;
    if (dist[a][b] != INF)
      cout << -1;
    else if (dist[b][a] != INF)
      cout << 1;
    else
      cout << 0;
    cout << '\n';
  }
  return 0;
}