[Python/파이썬] 백준 9466번 텀 프로젝트

9466번: 텀 프로젝트

문제

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

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

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

1234567

3

1

3

7

3

4

6

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

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

입력

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

출력

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

코드

import sys
sys.setrecursionlimit(int(1e7))

def dfs(selected, visited, cycle, x):
    global team
    visited[x] = True
    cycle.append(x)
    
    if not visited[selected[x]]:
        dfs(selected, visited, cycle, selected[x])    # 재귀호출
    else:   # 이미 방문한 노드 나옴
        if selected[x] in cycle:
            team += cycle[cycle.index(selected[x]):]
        return

for _ in range(int(input())):
    n = int(input())
    selected = [0] + list(map(int, input().split()))
    visited = [False] * (n+1)   
    
    team = []
    
    for i in range(1, n + 1):
        cycle = []
        if not visited[i]:
            dfs(selected, visited, cycle, i)
    print(n - len(team))

처음에 재귀 깊이를 충분히 설정해주지 않아서 RecursionError 발생...

재귀를 이용하여 문제를 풀 때는 반드시 재귀 깊이를 충분하게 설정해주도록 하자

 

문제를 보니 사이클에 포함이 되면 팀을 이룰 수 있다는 말인 것 같아서 방향 그래프에서 사이클을 찾는 방법을 찾아보고ㅗ 문제를 풀이하였다. 사이클에 포함되지 못하고 곁다리로 남겨진 친구들이 바로 팀을 구성하지 못한 친구들이다.

위 사진에서 5번 노드 같은 경우가 팀을 이루지 못한 경우이다.

이를 찾기 위해 dfs를 이용하였다. dfs를 이용하여 탐색하다가 이미 방문한 노드를 만나면 사이클이 발생한 것이므로 이때 사이클을 이루는 노드들을 저장해준다. 모든 노드에 대해 dfs를 돌리고 사이클을 이루는 노드의 갯수를 전체 노드의 개수에서 빼주면 정답이다.