텀 프로젝트

1. 개요

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

2. 풀이

import sys

def solution():

    # 입력함수
    INPUT = lambda: sys.stdin.readline().rstrip()
    READINT = lambda: int(INPUT())
    READWISH = lambda: [int(v)-1 for v in INPUT().split()]
    
    # 테스트케이스의 수
    T = READINT()

    def projects():
        answer = []
        
        for _ in range(T):
            answer.append(str(project(READINT(), READWISH())))
        return "\n".join(answer)

    def project(n, wish):
        traced, team = set(), set()
        
        for i in range(n):
            if i in traced:
                continue

            node = i
            pushed, pushedSet = [], set()
            
            # 각 노드들에 대해 dfs를 시행한다
            # 사이클이 발생하면 (이전에 방문한 노드를 다시 방문하면) 팀 구성이 가능하다.            
            while node not in traced:
                traced.add(node)
                pushed.append(node)
                pushedSet.add(node)
                node = wish[node]

            # 가장 마지막 방문한 노드를 방문한기록이 있으면 팀으로 구성된 인원에 추가한다.
            if node in pushedSet:
                team.add(node)
                while pushed and pushed[-1] != node:
                    team.add(pushed.pop())

        # 전체 학생수에서 팀으로 구성된 인원을 빼서 반환한다.
        return n-len(team)

    return projects()

print(solution())