[C/C++] 백준 #1613 역사(플로이드 와샬)

이번 문제는 역사적 사건의 전후 관계가 주어졌을 때, 그 관계를 이용해서 다른 두 사건의 선후관계를 유추하는 방법입니다.  선후 관계가 있으니, 위상 정렬을 사용할 수도 있는데, 저는 그것보다는 유향 그래프라고 생각하고 플로이드 와샬(Floyd Warshall) 알고리즘을 이용했습니다.

 

플로이드 와샬 알고리즘을 이용하면 모든 정점 사이의 연결관계를 파악할 수 있습니다.  하지만, 알고리즘의 점근적 분석이 \(O(V^3)\)이라는 단점이 있죠.  모순이 생기지 않는 연결관계이므로 사실 \(O(V^3)\)번 반복할 필요는 없습니다.  그렇지만 그냥 오리지날 플로이드 와샬 알고리즘을 이용해서 풀었습니다.

 

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

1613번: 역사

 

플로이드 와샬 알고리즘은 모든 정점간 사이를 파악하는데 사용합니다.  음의 가중치가 있을 때도 사용할 수 있는 장점이 있죠.  그리고 간선의 가중치가 사실 의미가 없기때문에 연결된 경우 1, 연결되지 않은 경우 0으로 설정했습니다.  플로이드 와샬 알고리즘은 초기에 주어진 간선들을 확장한다고 보시면 됩니다.

 

플로이드 와샬 알고리즘

 

제가 작성한 소스입니다.  소스는 참고용으로 봐주세요.

//----------------------------------------------------------------------------------------
//	baekjoon #1613
//		- by Aubrey Choi
//		- created at 2019-11-13
//----------------------------------------------------------------------------------------
#include <stdio.h>

int main()
{
	int n, m, a, b; static char adj[400][400];
	scanf("%d%d",&n,&m);
	while(m--) { scanf("%d%d",&a,&b); adj[a-1][b-1]=1; }
	for(int k=0;k<n;k++) for(int i=0;i<n;i++) for(int j=0;j<n;j++)
	{
		if(i==j||adj[i][j]) continue;
		adj[i][j]=(adj[i][k]&&adj[k][j]);
	}
	scanf("%d",&m);
	while(m--) { scanf("%d%d",&a,&b); a--,b--; printf("%d\n",adj[a][b]?-1:adj[b][a]?1:0); }
}