C++ / 백준 / 1613 / 역사

문제

 

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

1613번: 역사

문제풀이

 

플로이드 와샬 알고리즘을 이용해 풀었다.

A B가 있을 때 A가 먼저 일어난 사건이면 history[A][B]는 -1이,

B가 먼저 일어난 사건이면 history[A][B]는 1이 된다.

A B C가 있을 때 A가 B보다 먼저 일어났고 B가 C보다 먼저 일어났으면,

삼단 논법에 의해 A는 C보다 먼저 일어난 사건 이게 된다.

따라서 삼중 반복문을 통해 [A][B] == -1이고 [B][C] == -1이면 [A][C] = -1로 바꾸면 된다.

반대로 [A][B] == 1이고 [B][C} == 1이면 [A][C] = 1로 바꾸면 된다.

 

			if (history[history1][mid] == 1 && history[mid][history2] == 1) {
				history[history1][history2] = 1;
			}
			else if (history[history1][mid] == -1 && history[mid][history2] == -1) {
				history[history1][history2] = -1;
			}
                
                        ===================================================================
                
			if (history[history1][mid] == -1 && history[mid][history2] == -1) {
				history[history1][history2] = -1;
				history[history2][history1] = 1;
			}

위아래 어느 코드로 돌려도 상관없다.

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);

	int N(0), K(0), S(0), idx(0);
	int history1(0), history2(0), mid(0);
	cin >> N >> K;
	vector<vector<int>>history(N + 1, vector<int>(N + 1, 0));

	for (idx = 0; idx < K; ++idx) {
		cin >> history1 >> history2;
		history[history1][history2] = -1;
		history[history2][history1] = 1;
	}

	for (mid = 1; mid <= N; ++mid) {
		for (history1 = 1; history1 <= N; ++history1) {
			for (history2 = 1; history2 <= N; ++history2) {				
				if (history[history1][mid] == 1 && history[mid][history2] == 1) {
					history[history1][history2] = 1;
				}
				else if (history[history1][mid] == -1 && history[mid][history2] == -1) {
					history[history1][history2] = -1;
				}
			}
		}
	}

	cin >> S;

	for (idx = 0; idx < S; ++idx) {
		cin >> history1 >> history2;
		cout << history[history1][history2] << '\n';
	}
}