BOJ 백준 1613 : 역사

시작하면서

　이번 문제는 플로이드-와샬 알고리즘(FloydWarshall Algorithm) 을 사용해 해결하는 문제이다.

BOJ 1613 - 역사

​

문제 이해

​ 이 문제는 사실 플로이드-와샬로 해결하지 않아도 되보이는 문제이다. 단순하게 문제를 만들면,

1. 전후 관계를 간선으로 만들고
2. 간선을 모두 이어둔 그래프를 만든 후
3. 앞의 사건이 먼저인지, 뒤의 사건이 먼저인지를 확인

​ 이렇게 3개의 과정을 좀 더 효율적인 방법으로 해결하면 되지만, 플로이드-와샬 알고리즘을 공부하면서 해결하는 문제이므로 플로이드-와샬 알고리즘으로 해결했다. 방법은 다음과 같다.

1. 사건의 전후 관계를 나타낼 그래프를 만들고, 모두 INT_MAX로 초기화한다.
2. 사건의 전후 관계를 인풋으로 받아서, 그래프에 1의 값으로 넣어준다.
3. 인풋을 전부 넣은 후에는 플로이드-와샬 알고리즘을 통해 그래프를 변경한다.
4. 조건에 맞게 답을 출력한다.

​ 여기서 문제에만 최적화하려면 굳이 그래프에 int를 사용하지 않고, 단순히 연결되어 있는지를 계속 확인하면서 bool 값을 사용해도 된다. 하지만 굳이 그렇게까지도 하지 않고, 플로이드-와샬 그대로 유지하겠다.

​

해결

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <math.h>
#include <limits.h>

using namespace std;

void Input(vector<vector<int>> &graph)
{
	int n, k;

	cin >> n >> k;

	graph.resize(n + 1);
	for (int i = 1; i <= n; i++)
	{
		graph[i].resize(n + 1);
		for (int j = 1; j <= n; j++)
		{
			graph[i][j] = (i == j) ? 0 : INT_MAX;
		}
	}

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

		graph[a][b] = 1;
	}
}

void DoFloydWarshall(vector<vector<int>> &graph)
{
	int n = graph.size() - 1;

	for (int t = 1; t <= n; t++)
	{
		for (int i = 1; i <= n; i++)
		{
			for (int j = 1; j <= n; j++)
			{
				if (graph[i][t] == INT_MAX)
				{
					continue;
				}

				if (graph[t][j] == INT_MAX)
				{
					continue;
				}

				if (graph[i][j] > graph[i][t] + graph[t][j])
				{
					graph[i][j] = graph[i][t] + graph[t][j];
				}
			}
		}
	}
}


void PrintAnswer(const vector<vector<int>>& graph)
{
	int s;

	cin >> s;

	for (int i = 0; i < s; i++)
	{
		int a, b;

		cin >> a >> b;

		if (graph[a][b] == INT_MAX)
		{
			if (graph[b][a] != INT_MAX)
			{
				cout << "1\n";
			}
			else
			{
				cout << "0\n";
			}
		}
		else
		{
			cout << "-1\n";
		}
	}
}

int main()
{
	// sync off
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	// sync off

	vector<vector<int>> graph;

	Input(graph);
	DoFloydWarshall(graph);
	PrintAnswer(graph);

	return 0;
}