[🥇3 / 백준 9466 / 파이썬] 텀 프로젝트

 

9466번: 텀 프로젝트

 

문제

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

학생들이(s₁, s₂, ..., s_r)이라 할 때, r=1이고 s₁이 s₁을 선택하는 경우나, s₁이 s₂를 선택하고, s₂가 s₃를 선택하고,..., s_r-1이 s_r을 선택하고, s_r이 s₁을 선택하는 경우에만 한 팀이 될 수 있다.

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

 

 

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

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

입력

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

출력

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

 

예제 입력  2 7 3 1 3 7 3 4 6 8 1 2 3 4 5 6 7 8

예제 출력  3 0

 

풀이

 

DFS를 통해 사이클을 만들지 못한 정점의 개수를 찾는 문제이다.

1번 정점부터 시작하여 연결된 간선을 따라가다 이미 방문한 노드에 도달하면, 지나온 노드가 사이클을 이룰 경우 사이클의 크기만큼 결과값에 제외하는 방식으로 문제를 해결했다.

 

처음엔 정점을 순환하며 무조건 첫 노드를 기준으로 하여 첫 노드를 방향으로 하는 정점이 나올 때에만 사이클로 취급했었는데, 시간초과에 걸리게 되었다.

2 3 4 5 … 99998 99999 100000 99998 과같은 입력이 들어왔을 때, 재방문을 하는 경우가 많이지기 때문이었다.

처음 생각했던 알고리즘대로 한다면 2부터 99997 정점까지 O(N^2)으로 순환했을 것이다. 

이미 방문한 정점은 다시 방문하지 않도록 작성하자.

 

import sys
input = sys.stdin.readline

for _ in range(int(input())):
    n = int(input())
    s = [0]+list(map(int,input().split()))
    visit = [False]*(n+1)
    r = 0
    for i in range(1,n+1):
        if visit[i]:
            continue
            
        stack = [i]
        d = dict()
        while True:
            visit[stack[-1]] = True
            
            if visit[s[stack[-1]]]:
                if s[stack[-1]] in stack:
                    r += len(stack)-stack.index(s[stack[-1]])
                break
            stack.append(s[stack[-1]])
            
    print(n-r)