5주차 과제 4. 텀 프로젝트 BEST 풀이

베스트 풀이 링크

베스트 풀이코드- simyoju님

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

t = int(input())

def dfs(cur):
    global cnt, visited, done
    # 방문처리
    visited[cur] = True
    next = students[cur]
    #print(next)
    if not visited[next]:
        dfs(next)
    else:
        if not done[next]: #사이클이 형성되었다.
            i = next
            while i != cur: #팀원 카운트
                cnt += 1
                i = students[i]
            cnt += 1 # 플러스 본인
    done[cur] = True

for _ in range(t):
    n = int(input())
    students = list(map(lambda x : int(x)-1, input().split()))
    visited = [False]*n
    done = [False]*n # 팀 매칭 여부 = 사이클 여부
    cnt = 0
    for i in range(n):
        if not visited[i]: #방문을 안했다면
            dfs(i)
    print(n-cnt)

베스트 풀이 선정 이유

싸이클을 확인하는 함수를 가독성있게 만들었기 때문이다.
또한 이 문제를 재귀를 이용하여 해결하려 했을 경우sys.setrecursionlimit(111111)가 코드에 포함되어 있지 않으면 런타임 에러가 뜨게 된다.
그 이유는 파이썬은 기본 재귀 깊이 제한이 1000으로 매우 얕은 편이다.
따라서 위와 같은 코드를 작성해 재귀 깊이 제한을 늘려 주어야 한다. 이렇게 사소하지만 중요한 내용을 작성하셨기 때문에 베스트 풀이로 선정했다.

느낀점

파이썬에서 재귀 깊이 제한이 1000으로 매우 얕은 편임을 잘 알지 못하고 있었다.
이 제한이 종종 코딩 테스트에서 재귀를 이용하여 푸는 문제들에 런타임 에러를 일으킨다는 사실을 깨닫는 시간이 되었다.
또한 sys.setrecursionlimit()를 이용하여 재귀 깊이 제한을 늘려 주어야 한다는 것도 알게 되는 시간이 되었다.