백준 1613 - 역사

문제 설명

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

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

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, K개의 (a, b) 쌍이 주어질 때 a가 b보다 먼저 일어난 사건을 의미한다.

쿼리 S개를 입력받아 전후 관계를 판단하여 출력하면 된다.

 

우선 해당 문제는 다양한 방법으로 풀 수 있다.

간단하게 모든 노드에서 출발하는 다익스트라를 구현하여 연결 관계를 파악할 수 있고 플루이드 와샬을 통해 모든 노드 간의 연결 관계를 파악할 수도 있다.

우선 구현이 간단한 플루이드 와샬을 살펴보자.

전후 관계를 입력받은 뒤 연결 관계를 단방향으로 설정한 후 모든 노드의 연결 여부를 파악하면 된다.

edges.resize(N + 1, vector<int>(N + 1, 0));
for (int i = 0; i < K; i++)
{
    int a, b;
    cin >> a >> b;

    edges[a][b] = 1;
}

for (int k = 1; k <= N; k++)
{
    for (int i = 1; i <= N; i++)
    {
        for (int j = 1; j <= N; j++)
        {
            if (i == j) continue;

            if (edges[i][k] + edges[k][j] == 2)
            {
                edges[i][j] = 1;
            }
        }
    }
}

이후 S개의 쿼리를 처리하면 된다.

cin >> S;

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

    //a가 먼저면 -1 b가 먼저면 1 모르면 0
    int result = edges[a][b];
    if (result == 0)
    {
        if (edges[b][a] != 0) cout << 1 << "\n";
        else cout << 0 << "\n";

        continue;
    }

    if (result > 0) 
    {
        //a->b 가능
        cout << -1 << "\n";
    }
	}

 

 

두 번째 풀이는 다른 분이 작성한 코드의 시간이 짧아 살펴보다 좋은 풀이라고 생각되어 작성한다.

핵심부터 설명하자면, 위상 정렬을 통해 전후 관계를 파악하며 비트마스크로 도달 여부를 체크하는 것이다.

for (int i=1; i<=n; i++)
{
    if (degree[i] == 0)
    {
        q.push(i);
    }
    route[i].set(i);
}

while (q.size() != 0)
{
    int tg = q.front();
    q.pop();

    for (auto e: edges[tg])
    {
        degree[e]--;
        route[e] |= route[tg];
        if (degree[e] == 0)
        {
            q.push(e);
        }
    }
}

위상 정렬의 특성상 동일한 댑스에 대한 정렬은 느슨하게 처리될 수 있지만 전후 관계는 확실히 정렬된다.

따라서 해당 문제에 적합한 알고리즘이다.

또한, 이 과정에서 비트마스크를 통해 도달 여부를 판단하면 아래와 같이 쉽게 쿼리를 처리할 수 있다.

cin >> s;
for (int i=0; i<s; i++)
{
    int v1, v2, ans;
    cin >> v1 >> v2;
    if (route[v2].test(v1))
        ans = -1;
    else if (route[v1].test(v2))
        ans = 1;
    else
        ans = 0;
    cout << ans << '\n';
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int N, K, S;

vector<vector<int>> edges;

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cout << fixed;

	cin >> N >> K;

	edges.resize(N + 1, vector<int>(N + 1, 0));
	for (int i = 0; i < K; i++)
	{
		int a, b;
		cin >> a >> b;

		edges[a][b] = 1;
	}

	for (int k = 1; k <= N; k++)
	{
		for (int i = 1; i <= N; i++)
		{
			for (int j = 1; j <= N; j++)
			{
				if (i == j) continue;

				if (edges[i][k] + edges[k][j] == 2)
				{
					edges[i][j] = 1;
				}
			}
		}
	}


	cin >> S;

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

		//a가 먼저면 -1 b가 먼저면 1 모르면 0
		int result = edges[a][b];
		if (result == 0)
		{
			if (edges[b][a] != 0) cout << 1 << "\n";
			else cout << 0 << "\n";

			continue;
		}

		if (result > 0) 
		{
			//a->b 가능
			cout << -1 << "\n";
		}
	}

	return 0;
}

---