[BOJ-1613] 역사(C++)

백준 1162 역사

 

1613번: 역사

 

문제 설명

 

 - 세준이는 역사의 전후 관계를 알고 있다.

 

 - 세준이가 알고 있는 역사 전후 관계를 바탕으로 주어진 사건들의 전후 관계도 알 수 있는지 판단하라.

 

 - 사건의 앞 번호가 먼저 일어났다면 -1

   사건의 뒤 번호가 먼저 일어났다면 1

   어떤지 모르면(유추할 수 없으면) 0

---

 

입력 값

 

 - 첫째 줄에 첫 줄에 사건의 개수 n, 사건의 전후 관계의 개수 k가 주어진다.

   ( 1<= n <= 400 / 1 <= k <= 50,000)

 

 - 다음  k줄에는 전후 관계를 알고 있는 두 사건의 번호가 주어진다.

   앞에 있는 번호의 사건이 뒤에 있는 번호의 사건보다 먼저 일어난 것이다.

 

 - 사건의 전후 관계가 모순인 경우는 없다.

 

 - 다음에는 알고 싶은 사건의 쌍 s가 주어진다.

   ( 1 <= s <= 50,000)

 

 - 다음 s줄에는 각각 서로 다른 두 사건의 번호가 주어진다.

   (사건의 번호는 1보다 크거나 같고, n보다 작거나 같은 자연수이다.)

---

 

 

예제

 

---

 

 

문제 분석

 

 - 이 문제는 사건의 전후 관계가 그래프 형태로 연결되어 있는 모습이다.

 

 - 단순하게 생각해보면, 두 사건 a, b가 주어졌을 때 어느 사건이 먼저 일어났는지 판단하는 방법은

   a에서 시작하여 연결된 모든 노드를 살펴보았을 때 b가 존재하는지 확인하거나

   b에서 시작하여 연결된 모든 노드를 살펴보았을 때 a가 존재하는지 확인하는 방법이다.

 

 - 즉, 한 사건당 k개를 모두 살펴보아야 하기 때문에 400x50000 = 20,000,000의 경우의 수가 생긴다.

   알고싶은 쌍 한개 당 2천만번 살펴보아야 한다. 결국 5만 x 2000만 = 1조 번 살펴보아야 한다.

   그러므로 이 방법은 불가능하다.

 

 - 이 문제는 출발 사건이 존재하고, 도착 사건이 존재한다.

   우리는 여기서 출발 -> 도착 사건으로 연결이 되어 있는지 판단할 수 있으면 되는 것이다.

 

 - 그러므로 플로이드-워셜 알고리즘을 이용하여 모든 노드간 최단 거리를 구하면 된다.

최단 경로 알고리즘 - 플로이드-워셜(Floyd-Warshall) 알고리즘

 

 - 사건의 개수는 최대 400개이기 때문에 $400^3$ = 64,000,000의 시간이 걸린다.

 

 - 해당 사건들 사이에 가중치는 따로 주어진 것이 없기 때문에 모두 1로 설정한다.

 

 - 이후, 플로이드-워셜을 통해서 각 사건들간의 최단 거리를 구한다.

 

 - 사건 a와 사건 b가 전후관계인지 판단하는 방법은 다음과 같다.

  0. 플로이드 워셜을 통해 각 사건들간 최단 거리가 저장된 배열을 d[i][j]라 하자(i->j 최단 거리)

  1. d[a][b] 가 초기 최대값 이상인지 판단한다.

  2. 미만이라면 d[a][b] 가 연결되어 있다는 것이기 때문에 -1을 리턴한다.

  3. 이상인 경우 d[b][a]가 초기 최대값 이상인지 판단한다.

  4. 미만이라면 b->a 형태로 사건이 연결되어 있기 때문에 1을 리턴한다.

  5. 이상인 경우 두 사건은 연결되어 있지 않기 때문에 0을 리턴한다.

 

 

 - 주의할 점

   1. 플로이드-워셜을 하기 위해 초기화 과정에서 최대 값을 INT_MAX로 넣게 되면 안된다.

      d[i][k] + d[k][j]를 실행해야 하는데 INT_MAX를 넣으면, 범위를 벗어나게된다. 

      모든 사건이 5만개 이하이기 때문에 최대 값은 50,001을 넣으면 된다.

 

   2. C++에서 출력 시 개행은 endl과 '\n'을 사용할 수 있다.

      endl은 출력 시 많은 시간이 걸리기 때문에 출력을 많이 해야 하는 경우 '\n'을 사용해야 시간초과되지 않는다.

---

 

 

소스 코드

 

#include <bits/stdc++.h>

using namespace std;

vector<int> v[401];

int visited[401][401];

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

	int n, k,s;

	fill(&visited[0][0], &visited[0][0] + 401 * 401, 50001);

	cin >> n >> k;
	for (int i = 0; i < k; i++) {
		int a, b;
		cin >> a >> b;

		visited[a][b] = 1;

	}

	for (int i = 1; i <= n; i++) {
		visited[i][i] = 0;
	}

	for (int k = 1; k <= n; k++) {
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				visited[i][j] = min(visited[i][j], visited[i][k] + visited[k][j]);
			}
		}
	}

	cin >> s;
	for (int i = 0; i < s; i++) {
		int a, b;
		cin >> a >> b;
		if (visited[a][b] >= 50001) {
			if (visited[b][a] >= 50001) {
				cout << 0 << "\n";
			}
			else {
				cout << 1 << "\n";
			}
		}
		else {
			cout << -1 << "\n";
		}
	}



	return 0;
}