[Python] boj no. 9466 : 텀 프로젝트

Problem

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

Idea

학생들의 선택의 결과는 학생을 노드로, 각 학생의 선택을 간선으로 하는 방향 그래프로 표현할 수 있다. 이 때, 팀은 그래프 내에서 사이클이 나타나는 경우에 생성된다. 즉, 학생 s1이 s2를, s2이 s3을 s3이 s1을 선택하는 경우에 생성된다. 따라서 그래프를 dfs로 순회하며 그래프 내의 사이클에 포함되는 노드의 수가 팀을 이루는 학생들의 수가 된다.

dfs를 통해 그래프 내의 사이클을 찾는 과정은 다음과 같다.

1. 임의의 한 노드에서부터 탐색을 시작한다.
2. 이미 방문한 적이 있는 노드에 다시 방문하게 될 경우 그래프 내에 사이클이 존재한다.
3. 이미 방문한 적이 있는 노드에 다시 방문하지 않는 경우 그래프 내에 사이클이 존재하지 않는다.

이 때, 문제의 경우 학생들의 선택에 따라 하나의 그래프가 아닌 여러 개의 그래프로 표현될 수 있다. 따라서 모든 노드에 대해 dfs를 수행하되 지금까지의 방문 여부를 나타내는 visited 리스트와 현재 탐색에서의 방문 여부를 나타내는 counted 리스트를 선언하여 visited == False인 노드에 대해서만 탐색을 수행한다.

또한, counted 리스트에 탐색 순서 값을 저장하여 탐색 도중 counted != 0 인 노드를 방문할 경우 counted[current] - counted[next] + 1 로 해당 사이클에 포함된 노드의 갯수를 알 수 있다. 또한 visited == True인 노드에 방문할 경우 탐색을 중단시켜 이미 계산된 사이클을 중복으로 세는 것을 방지한다.

dfs는 스택을 이용하여 구현하였다.

Code

import sys
from collections import deque

input = sys.stdin.readline

def dfs(idx):
    global party
    stack = deque()
    cur = idx
    cnt = 1
    
    while True:
        stack.append(cur)
        counted[cur] = cnt
        next = edge[cur]
        
        if visited[next]:
            break
        
        if counted[next] == 0:
            cnt += 1
            cur = next
        else:
            party += (cnt - counted[next] + 1)
            break
        
    while stack:
        node = stack.pop()
        visited[node] = True
    
T = int(input())
for _ in range(T):
    n = int(input())
    visited = [False for _ in range(n+1)]
    counted = [0 for _ in range(n+1)]
    edge = [0] + list(map(int, input().split()))
    party = 0
    
    for i in range(1, n+1):
        if visited[i] == False:
            dfs(i)
    
    print(n - party)

Comment