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

백준 9466

앞에 두 명처럼 지목한 사람들끼리 사이클을 형성하게 되면 같은 팀이 된다.
깊이 우선 탐색으로 부모 노드(지목한 사람)를 리스트에 추가하면서, 지목 당한 사람이 지목한 사람들 리스트에 포함 되어있다면 팀으로 만들어 준다.

T = int(input())
for _ in range(T):
    N = int(input())
    selected = [0] + list(map(int, input().split()))

    visited = [False] * (N+1)
    team_mems = 0

    def dfs(i):
        global team_mems

        visited[i] = True # 나부터
        team.append(i) # 팀 후보에 추가
        select = selected[i] # 다음 사람 지목

        if visited[select]: # 지목한 사람을 이미 방문했을 경우
            if select in team: # 그 사람이 팀 후보에 있다면
            	# 그 사람부터 이후에 팀에 들어온 사람들은 한 팀이 된다
                team_mems += len(team[team.index(select):])
        else: # 아니라면 지목 받은 사람이 다른 사람 지목
            dfs(select)

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

    print(N - team_mems)

팀을 구성하는 부분

team_mems += len(team[team.index(select):])

은 위 예제로 본다면

1 → 3: 팀 [1, 3]
3 → 3: 팀 [3], 사이클에 해당하는 부분만 팀으로 만들어줘야 한다. 같은 번호가 처음으로 등장하는 사람이 가장 처음 팀의 멤버다.

2 → 1: 팀 [], 1번은 이미 다른 사람 지목해서 팀에 추가되지 않는다. 방문은 했으므로 dfs 함수의 첫 번째 조건문 중 참, 함수 종료
4 → 7: 팀 [4, 7]
7 → 6: 팀 [4, 7, 6]
6 → 4: 팀 [4, 7, 6]

따라 [3], [4, 7, 6] 두 팀만 생기고 다른 1, 2, 5번은 팀이 정해지지 않는다.