백준 14757 - Dueling Philosophers (C++)

문제

• 문제 링크

  
   BOJ 14757 - Dueling Philosophers 
  

• 문제 요약

에세이의 위계 관계가 유향 그래프 형태로 주어진다.
이를 토대로 배열을 구성할 때, 배열이 존재하는지, 존재 한다면 유일할지 다양할지를 판단해보자.

• 제한

TL : $2$ sec, ML : $512$ MB




$1 ≤ n ≤ 1,000$

$1 ≤ m ≤ 500,000$

알고리즘 분류

• 그래프 이론(graphs)
• 위상 정렬(topological_sort)

풀이

위상 정렬 문제임은 쉽게 알아챌 수 있다.
즉, 위상 정렬을 기본적으로 잘 이해하고 있는지를 묻는 문제이다.

우선 배열이 존재하지 않을 조건을 생각해보자.
이는 간단히, 위상 정렬상에 등장하지 않은 정점이 있는지를 보면 된다.

그럼 배열이 유일한지 다양한지는 어떻게 판단할 수 있을까?
이 또한 위상 정렬이 갖는 특성에 기반해 생각해보면, 쉽게 판단할 수 있다.

$u→v$의 관계가 주어질 때마다 $v$의 $indegree$를 $1$씩 올려준다고 할 때, $indegree$가 $0$인 정점을 시작으로 위상 정렬을 진행한다고 해보자.

만약 배열이 유일하다면, 각 $depth_1, depth_2, ... depth_n$에서 등장하는 정점은 단 하나여야 한다. 즉, $DAG$의 모양이 하나의 직선이 되어야 한다.

결과적으로 이는 매 순간마다 큐의 잔여 용량을 보고 판단해낼 수 있다.
자세한 건 아래 코드를 참조하자.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
vector <int> Gr[1001];
int n, m, ind[1001];
 
void Init()
{
    for (int i{}; i < 1001; i++)
        ind[i] = 0, Gr[i].clear();
 
    for (int i, j; m--;)
    {
        cin >> i >> j;
        Gr[i].push_back(j);
        ind[j]++;
    }
}
void Solve(int ans = 1)
{
    queue <int> Q;
    for (int i(1); i <= n; i++)
        if (!ind[i])
            Q.push(i);
 
    while (Q.size())
    {
        int now(Q.front()); Q.pop();
 
        if (Q.size()) ans = 2;
 
        for (int& next : Gr[now])
            if (!--ind[next])
                Q.push(next);
    }
    for (int i(1); i <= n; i++)
        if (ind[i])
            ans = 0;
 
    cout << ans << '\n';
}
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    while (cin >> n >> m, n)
    {
        Init();
        Solve();
    }
}

comment

끝