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

 

 

문제 링크

 

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

9466번: 텀 프로젝트

 

 

문제 풀이

 

정답률이 낮은 이유가 있던 문제였습니다. 메모리와 시간의 압박이 쎘습니다,,ㅠㅠ

결국 이 문제의 핵심은 학생들 간 사이클을 파악하는 것입니다.

팀을 이룰 수 있는 경우는 두 가지입니다.

1) 본인이 본인을 선택하는 경우

2) 1 -> 2 -> 3 -> 1 이렇게 이어진 형태로 서로를 지목하는 경우

1번 학생부터 for문을 돌려서 확인했습니다.

지목한 사람을 타고타고 가다가 만약 이전에 체크한 학생을 지목했을 경우

해당 학생이 그 사이클에 존재하는지를 확인하고 맞다면 그 사이클은 팀을 이루게됩니다.

이렇게 사이클을 이룬 학생들을 student 배열에 넣어주고,

팀을 이루지 못한 학생들을 출력해야하므로 n에서 len(student)를 빼서 출력해주었습니다.

 

import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline

def dfs(start, arr):
    visited[start] = 1
    cycle.append(start)
    num = nums[start]
    if visited[num]:
        if num in cycle:
            arr += cycle[cycle.index(num):]
        return
    else:
        dfs(num, arr)

for _ in range(int(input())):
    n = int(input())
    nums = [0] + list(map(int, input().split()))
    visited = [0 for _ in range(n + 1)]
    # 팀을 이룬 학생
    student = []
    for now in range(1, n + 1):
        if not visited[now]:
            cycle = []
            dfs(now, student)
    print(n - len(student))