[백준9466번] 텀 프로젝트 / Python3

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

1	2	3	4	5	6	7
3	1	3	7	3	4	6

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

예제 입력 1

2
7
3 1 3 7 3 4 6
8
1 2 3 4 5 6 7 8

예제 출력 1

3
0

나의 풀이

해당 문제는 DFS로 각 학생들을 방문했는지를 담는 visited와 팀매칭이 끝났는지를 담는 done이라는 두 가지의 리스트를 가지고 문제를 풀어야했다. 우선 DFS로 1번부터 마지막 학생까지 반복을 하면서 DFS로 방문 여부를 확인하며 순환을 찾기 시작한다. 여기서 아래와 같이 경우의 수가 나뉜다.

• 현재 학생이 가리키는 학생을 아직 방문하지 않음
• 현재 학생이 가리키는 학생이 이미 방문을 함

학생이 아직 방문을 하지 않았다면 그 학생으로 DFS를 한 단계 더 진행을 한다. 그러나 2번째의 경우 이미 방문한 경우이다. 이 경우는 또 아래와 같이 두개의 경우로 나뉜다.

• 현재 학생이 가리키는 학생의 done이 True. 즉, 이미 팀매칭이 끝난 경우
• 현재 학생이 가리키는 학생의 done이 False. 즉, 순환이 찾아진 경우

만약 done이 True인 학생을 가리킨다면 이미 그 학생은 순환이 있어 팀이 만들어졌고 현재 학생과는 순환이 만들어지지 않는다는 의미와 같다. 따라서 현재 학생은 팀이 생기지 않고 팀 매칭이 끝나는 것이다. 그러므로 현재 학생의 done을 True로 바꾸어주면 된다. 반대로 done이 False라면 순환이 발생하여 팀이 생성되는 경우이다. 이 경우 순환이 발생하는 모든 학생들의 카운트를 세주고 현재 학생의 팀매칭이 끝났으니 done을 True로 바꾸어준다. 이렇게 모든 학생을 방문하게되면 카운트 변수는 팀이 이루어진 학생들의 수가 되므로 전체 학생 수에서 카운트를 빼준 값을 반환해주면 문제는 해결된다.

단, python3로는 재귀의 깊이가 한정되어 있어 런타임에러가 발생할 수 있다. 필자는 sys.setrecursionlimit(111111)로 재귀의 깊이를 늘려주었다.

코드

# 9466번 텀 프로젝트
import sys

sys.setrecursionlimit(111111)
def dfs(cur):
    global visited, cnt, done

    visited[cur] = True
    ns = students[cur-1]
    if not visited[ns]:
        dfs(ns)
    else:
        if not done[ns]:
            i = ns
            while i != cur:
                cnt += 1
                i = students[i-1]
            cnt += 1
    done[cur] = True

t = int(sys.stdin.readline())

for _ in range(t):
    n = int(sys.stdin.readline())
    students = list(map(int, sys.stdin.readline().split()))
    cnt = 0
    done = [False] * (n+1)
    visited = [False] * (n+1)

    for i in range(1, n+1):
        if not visited[i]:
            dfs(i)

    print(n - cnt)