[백준 9466] 텀 프로젝트

문제

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

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

 

입력

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

 

출력

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

---

접근

순환하는 노드를 찾고 이에 해당하지 않은 노드들을 최종해로 출력한다. 방문한 노드를 리스트에 추가하다가 한 번 방문한 노드를 다시 방문했을 때 해당 노드부터 마지막 노드까지를 순환하는 노드라고 판단한다.

 

구현

- 1번 학생부터 방문하지 않은 노드라면 DFS를 시작하며 graph에 노드들을 넣어준다. 

for _ in range(test_case):
    N = int(input())
    tree = [0] + list(map(int, input().split()))
    visited = [False] * (N+1)
    answer = []

    for i in range(1, N+1):
        if not visited[i]:
            graph = []
            DFS(i)

- 현재 방문한 노드를 방문 표시하고 graph에 추가한다.

- 이후 다음 방문한 노드를 꺼내서 방문하지 않았다면 재귀호출로 다음 DFS를 실행한다.

- 이미 방문했다면 graph 내에서 해당 노드의 위치를 찾고 마지막 노드까지 리스트 answer에 넣는다.

- 이미 방문한 노드를 또 방문한 것은 순환하는 그래프이기 때문에 DFS를 실행하지않고 종료한다. 

def DFS(node):
    global answer
    visited[node] = True
    graph.append(node)
    next_node = tree[node]
    if visited[next_node]:
        if next_node in graph:
            answer += graph[graph.index(next_node):]
        return
    else:
        DFS(next_node)

- 최종적으로 N에서 answer의 길이만큼 뺀 것이 최종해가 된다.

---

전체 코드

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

test_case = int(input())

def DFS(node):
    global answer
    visited[node] = True
    graph.append(node)
    next_node = tree[node]
    if visited[next_node]:
        if next_node in graph:
            answer += graph[graph.index(next_node):]
        return
    else:
        DFS(next_node)

for _ in range(test_case):
    N = int(input())
    tree = [0] + list(map(int, input().split()))
    visited = [False] * (N+1)
    answer = []

    for i in range(1, N+1):
        if not visited[i]:
            graph = []
            DFS(i)

    print(N - len(answer))