BOJ 9466 - 텀 프로젝트 링크
(2023.05.22 기준 G3)

문제

모든 학생들은 프로젝트를 같이 하고 싶은 학생을 한 명만 선택을 한다. 선택이 사이클을 이룰 때 한 팀이 될 수 있다고 했을 때, 어느 프로젝트 팀에도 속하지 않는 학생들의 수 출력

알고리즘

DFS 응용

풀이

결론부터 말하자면, DFS를 통해 방문한 정점을 만날 때까지 탐색하면서 스택에 방문한 정정점을 쌓으면서 찾고, 찾은 정점을 다시 스택에 쌓은 역순으로 pop하면서 찾으면서 사이클 유무를 판별하면 된다.

이런 그래프가 있다고 생각하자.
이제 우린 1번부터 차례대로 DFS를 통해 방문한 정점에 도달할 때까지 계속 탐색할 것이다.

1번부터 시작하면 1->3->4->5 순서대로 탐색을 하게 되고 5에서 다시 3으로 갈 땐, 3이 이미 방문한 정점이므로 3을 찾은 것이다.

그럼 이제 스택에서 찾은 정점인 3을 찾을 때까지 pop하면 5, 4, 3 순서대로 찾게 되고, 이 사이클의 크기는 3이라는 것을 알 수 있다.

그럼 이제 2번으로 탐색을 해보자.2번이 가르키는 1번은 이미 방문했던 정점이므로 스택에는 2만 쌓이게 된다. 우리가 찾은 정점은 1번이므로 스택에서 1번을 찾을 때까지 pop을 해야 한다. 하지만 스택에는 1번 정점이 없으므로 이번에는 사이클을 찾지 못한 것이다.

이러한 방법으로 진행해주면 된다.

코드

• C++

#include <bits/stdc++.h>
using namespace std;

int choice[100001];
bool visited[100001];
stack<int> stk;

int dfs(int i){
    // 정점을 방문한 순서대로 스택에 쌓는다.
    visited[i] = true;
    stk.push(i);

    // 만약 다음 정점이 방문한 정점이라면 그 정점을 반환한다.
    if (visited[choice[i]]) return choice[i];
    return dfs(choice[i]);
}

void solve(){
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> choice[i];

    fill(visited + 1, visited + n + 1, false);
    int result = n;
    for (int i = 1; i <= n; i++){
        if (visited[i]) continue;

        // 사이클의 기준점이 될 수 있는 정점을 찾자.
        while (!stk.empty()) stk.pop();
        int cycle_vertex = dfs(i);

        // 방문 순서의 역순으로 정점을 하나씩 뽑아서
        // 위에서 찾은 기준점을 찾는다면 지금까지 뽑은 정점들은 사이클을 이룬다.
        int sz = 0, vertex;
        while (!stk.empty()){
            vertex = stk.top(); stk.pop();
            sz++;
            if (vertex == cycle_vertex){
                result -= sz;
                break;
            }
        }
    }

    cout << result << '\n';
}

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

    int T;
    cin >> T;
    while (T--) solve();
}

• Python

import sys; input = sys.stdin.readline
sys.setrecursionlimit(1000000)

def dfs(i):
    # 정점을 방문한 순서대로 스택에 쌓는다.
    visited[i] = True
    stack.append(i)

    # 만약 다음 정점이 방문한 정점이라면 그 정점을 반환한다.
    if visited[choice[i]]:
        return choice[i]
    return dfs(choice[i])

for _ in range(int(input())):
    n = int(input())
    choice = [0] + list(map(int, input().split()))

    visited = [False] * (n + 1)
    result = n
    for i in range(1, n + 1):
        if visited[i]:
            continue

        # 사이클의 기준점이 될 수 있는 정점을 찾자.
        stack = []
        cycle_vertex = dfs(i)

        # 방문 순서의 역순으로 정점을 하나씩 뽑아서
        # 위에서 찾은 기준점을 찾는다면 지금까지 뽑은 정점들은 사이클을 이룬다.
        sz = 0
        while stack:
            vertex = stack.pop()
            sz += 1
            if vertex == cycle_vertex:
                result -= sz
                break

    print(result)