백준 Topology Sort

[백준] 9466. 텀 프로젝트

Posted by Jun Blog on Tuesday, December 29, 2020

문제 설명

문제 : 백준 9466번 - 텀 프로젝트

학생들은 프로젝트 팀을 구성하기 위해 프로젝트를 함께하고 싶은 1명의 학생을 선택해야한다.
자기자신을 선택하는 경우도 있다. (이 경우도 팀으로 간주)

학생들이$(s_1, s_2, …, s_r)$이라 할 때, r=1이고 $s_1$이 $s_1$을 선택하는 경우나, $s_1$이 $s_2$를 선택하고, $s_2$가 $s_3$를 선택하고,…, $s_{r-1}$이 $s_r$을 선택하고, $s_r$이 $s_1$을 선택하는 경우에만 한 팀이 될 수 있다.

학생들이 선택한 결과를 통해 팀으로 구성되지 않는 학생들의 수를 출력한다.

Solution

문제에서 팀이 성립되는 경우는 선택한 학생들간에 사이클을 형성하는지 여부이다.
따라서 학생들이 선택한 결과를 통해 팀으로 구성되지 않는 학생들을 구하라는 말인즉슨 사이클을 형성하지 않는 학생들을 구하라는 말과도 동일하다.

문제에서 주어진 예시케이스를 가지고 방향 그래프를 구성하면 다음과 같아지며 학생들 중 $(3)$, $(4, 6, 7)$이 사이클을 형성하고 있음을 확인할 수 있다.

1234567
3137346

사이클을 판별하기 위해 DFS를 사용할 수도 있고, 위상정렬을 사용할 수도 있다.
본인은 문제를 해결하기위해 위상정렬을 사용하였다.
위상정렬은 사이클이 발생한 노드들에 대해서는 위상정렬을 수행할 수 없게되므로 DAG(Directed Acyclic Graph)에만 적용이 가능하다.
즉, 사이클이 발생하기 전까지는 위상정렬을 수행할 수 있다. 이 부분에 착안하여 본 문제에서는 요구하고 있는 사이클이 발생하지 않은 학생들의 수를 구하기위해 사이클이 발생하기 전까지 정렬이 수행되는 횟수를 카운트해주기로 했다.

수행단계 (위상정렬)

  1. 학생들이 선택한 결과를 통해 방향 그래프를 구성한다.
  2. 첫번째부터 마지막까지 순회하여 진입차수가 0인 학생들을 큐에 삽입한다.
  3. 사이클이 발생하지 않는 경우를 카운트한다.
    1. 큐의 front에 있는 노드와 연결된 다른 노드들의 진입차수를 1만큼 감소시킨다.
    2. 연결된 다른 노드 중 진입차수가 0인 노드를 큐에 삽입한다.
    3. 큐의 front에 있는 노드를 제거한다.
    4. 카운트 값을 증가시킨다.
    5. 큐가 empty일 때까지 반복한다.

주어진 예시케이스를 가지고 위의 단계들을 수행하면 3명의 학생들이 팀을 구성하지 못하는 것을 알 수 있다.

  • 진입차수가 0인 2와 5를 큐에 삽입한다. (카운트는 2)

  • 큐에서 2를 꺼내고 2와 연결된 1의 진입차수를 감소시킨다. 이 때, 1은 진입차수가 0이 되므로 큐에 삽입한다. (카운트는 3)
    큐에서 5를 꺼내고 5와 연결된 3의 진입차수를 감소시킨다.

  • 큐에서 1을 꺼내고 1이랑 연결된 3의 진입차수를 감소시킨다.

  • 큐가 비었으므로 반복을 종료한다.

Code

위상정렬을 사용한 코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

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

    int tc;
    cin >> tc;
    while(tc-- > 0){
        int n, ans = 0;
        vector<vector<int>> graph;
        vector<int> indegree;
        queue<int> q;

        cin >> n;

        graph.resize(n+1);
        indegree.resize(n+1);

        //그래프 생성
        for(int from=1; from<=n; from++){
            int to;
            cin >> to;
            graph[from].push_back(to);
            indegree[to]++;
        }

        //진입차수가 0인 그래프 탐색
        for(int i=1; i<=n; i++){
            if(indegree[i] == 0) q.push(i);
        }

        while(!q.empty()){
            int cur = q.front();
            ans++;
            q.pop();

            //진입차수 제거
            for(int next : graph[cur]){
                indegree[next] -= 1;

                //새롭게 진입차수가 0이 되는 노드 삽입
                if(indegree[next] == 0){ 
                    q.push(next);
                }
            }
        }

        cout << ans << '\n';
    }
}
CATALOG