[플로이드–와샬] (백준 1613) 역사

알고리즘

플로이드-와샬

 

[문제 본문]

문제

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

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

입력

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

출력

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

제한

예제 입력 1

5 5
1 2
1 3
2 3
3 4
2 4
3
1 5
2 4
3 1

예제 출력 1

0
-1
1

힌트

 

[푼 코드]

#include <iostream> 
#define MAXNUM 401 
#define INF 987654321
using namespace std;

int n, k;
int arr[MAXNUM][MAXNUM];

void Solved()
{
	for (int k = 1; k <= n; k++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (arr[i][j] > arr[i][k] + arr[k][j])
				{
					arr[i][j] = arr[i][k] + arr[k][j];
				}
			}
		}
	}

}

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

	cin >> n >> k;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= n; j++)
		{
			arr[i][j] = INF;
		}
	}

	int a, b;
	for (int i = 0; i < k; i++)
	{
		cin >> a >> b;
		arr[a][b] = 1;
	}

	Solved();

	int ans[50001];
	int tc;
	cin >> tc;
	for (int i = 0; i < tc; i++)
	{
		cin >> a >> b;
		if (arr[a][b] != INF)
		{
			ans[i] = -1;
		}
		else if (arr[b][a] != INF)
		{
			ans[i] = 1;
		}
		else
		{
			ans[i] = 0;
		}

		/*if (arr[a][b] != INF)
		{
			cout << -1 << '\n';
		}
		else if (arr[b][a] != INF)
		{
			cout << 1 << '\n';
		}
		else
		{
			cout << 0 << '\n';
		}*/
	}

	for (int i = 0; i < tc; i++)
	{
		cout << ans[i] << '\n';
	}
	return 0;
}

주석과 같이 입력받자마자 출력을 한다면 시간 초과 납니다.

입력과 출력을 반복하여 사용하는 형식으로 구성하면 느려지는 것 같습니다. 자세한 것은 찾아봐야겠네요.

 

컨텍스트 스위칭은 다음과 같은 상황에서 일어난다.

1. I/O interrupt

2. CPU 사용시간 만료

3. 자식 프로세스 Fork

4. 인터럽트 처리를 기다릴 때

 

#플로이드-와샬 #알고리즘 #백준 #최단거리알고리즘 #백준1613