[백준] 1613번 - 역사 (C++) 문제 및 풀이

문제) 백준 - 플로이드 와샬 - 역사

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

1613번: 역사

 

전/후 관계가 있는 역사 사건들이 주어질 때, 임의의 두 사건의 전/후 관계를 구하는 문제였습니다. 사건의 개수가 최대 400이므로 플루이드 와샬 알고리즘(O(N^3))으로 해결할 수 있습니다. >, < 관계를 1, -1로 저장하여 같은 전/후 관계끼리만 비교가 가능하므로 update 합니다.

 

C++ 소스코드)

	#include <bits/stdc++.h>
	#define endl "\n"
	#define MAX 401
	#define int long long
	using namespace std;
	typedef pair<int, int> p;
	int N, K;
	int board[MAX][MAX];
	signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N >> K;
	for(int i = 0; i < K; ++i){
	int a, b;cin >> a >> b;
	board[a][b] = -1;
	board[b][a] = 1;
	}
	for(int t = 1; t <= N; ++t)
	for(int i = 1; i <= N; ++i)
	for(int j = 1; j <= N; ++j)
	if(board[i][t] == board[t][j] && board[i][t] != 0)
	board[i][j] = board[i][t];
	int tc; cin >> tc;
	while(tc--){
	int a, b; cin >> a >> b;
	cout << board[a][b] << endl;
	}
	return 0;
	}

view raw 1613.cpp hosted with ❤ by GitHub