백준 알고리즘 1613번 : 역사

링크

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

문제

역사, 그 중에서도 한국사에 해박한 세준이는 많은 역사적 사건들의 전후 관계를 잘 알고 있다. 즉, 임진왜란이 병자호란보다 먼저 일어났으며, 무오사화가 기묘사화보다 먼저 일어났다는 등의 지식을 알고 있는 것이다.

세준이가 알고 있는 일부 사건들의 전후 관계들이 주어질 때, 주어진 사건들의 전후 관계도 알 수 있을까? 이를 해결하는 프로그램을 작성해 보도록 하자.

입력

첫째 줄에 첫 줄에 사건의 개수 n(400 이하의 자연수)과 알고 있는 사건의 전후 관계의 개수 k(50,000 이하의 자연수)가 주어진다. 다음 k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다. 이는 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어났음을 의미한다. 물론 사건의 전후 관계가 모순인 경우는 없다. 다음에는 사건의 전후 관계를 알고 싶은 사건 쌍의 수 s(50,000 이하의 자연수)이 주어진다. 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다. 사건의 번호는 1보다 크거나 같고, N보다 작거나 같은 자연수이다.

출력

s줄에 걸쳐 물음에 답한다. 각 줄에 만일 앞에 있는 번호의 사건이 먼저 일어났으면 -1, 뒤에 있는 번호의 사건이 먼저 일어났으면 1, 어떤지 모르면(유추할 수 없으면) 0을 출력한다.

예제 입력 및 출력

풀이법

... 그냥 엄청나게 틀린 문제다. 알고리즘은 완벽한 데 구현한 플로이드-와샬 알고리즘 코드 자체에 문제가 있어서 계속 틀린 문제...
n이 400이므로 플로이드-와샬 알고리즘을 사용해서 찾아주면 된다.
입력으로 들어오는 사건중 앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어난 사건이므로 dist[u][v] = 1을 이용해서 입력을 받아주면 된다.
dist배열을 초기화할 때 자기자신으로 가는 경우는 없으므로 모든 배열을 INF(1e9)로 초기화 해주면 된다.
플로이드 탐색을 진행한 후에는 각 물음을 답해주면 되는데,

A에서 B로 갈 수 있다면 A사건이 B보다 먼저 일어났다는 뜻이고, B에서 A로 갈 수 있다면 B사건이 A보다 먼저 일어났다는 뜻이다.

만약 둘 다 없다면(경로가 INF이면) 유추할 수 없는 사건이다.

풀이 코드(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 401
#define INF 1e9
#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(int n){
  for(int k = 1; k <= n; k++){ // k : 거쳐가는 정점
    for(int i = 1; i <= n; i++){ // i : 행(출발 정점)
      for(int j = 1; j <= n; 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,s;

int main(){
  fastio;
  cin >> n >> m;
  resetGraph();
  for(int i = 0; i < m; i++){
    int u,v;
    cin >> u >> v;
    dist[u][v] = 1; // u가 v보다 먼저 일어남
  }
  floyd(n);
  cin >> s;
  while(s--){
    int a,b;
    cin >> a >> b;
    if(dist[a][b] == INF && dist[b][a] == INF) cout << 0 << "\n";
    else if(dist[a][b] != INF) cout << -1 << "\n";
    else if(dist[b][a] != INF) cout << 1 << "\n";
  }
  return 0;
}

복습

#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define sz(a) int((a).size())
#define fastio ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define MAX(a, b) (((a) > (b)) ? (a) : (b))
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>;
using wector = vector<vector<int>>;
using tii = tuple<int,int,int>;

const int INF = int(1e9) + 1;

int dist[401][401],n,m;

void reset(){
  for(int i = 0; i <= n; i++){
    for(int j = 0; j <= n; j++){
      dist[i][j] = i==j ? 0 : INF;
    }
  }
}

void floyd(){
  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]);
      }
    }
  }
}

int main() {
	fastio;
  cin >> n >> m;
  reset();
  for(int i = 0; i < m; i++){
    int a,b; cin >> a >> b;
    dist[a][b] = 1;
  }
  floyd();
  int k; cin >> k;
  for(int i = 0; i < k; i++){
    int a,b; cin >> a >> b;
    if(dist[a][b] == INF && dist[b][a]==INF) cout << 0 << "\n"; // 몰라
    else if(dist[a][b] != INF) cout << -1 << "\n"; // 앞에 있는 사건 먼저
    else if(dist[b][a] != INF) cout << 1 << "\n"; // 뒤에 있는 사건 먼저
  }
  return 0;
}