[그래프, DFS] 백준 9466. 팀정하기

백준 9466번 텀 프로젝트 문제다. 문제의 원리에 cycle의 개념을 떠올려야 하고 재귀함수 사용시, 필수적으로 사용되는 sys.setrecursionlimit 함수가 필요한 이유를 배울 수 있었다.

이 문제는 순환구조로써 서로를 지목한 학생끼리 팀을 꾸리게 하고, 팀이 정해지지 않은 그 외의 학생들의 수를 출력하는 문제이다.

 

 

* 패턴

이 문제는 학생을 지목하고, 지목된 학생의 지목된 학생을 찾는 식으로 진행된다. 이처럼 DFS문제는 재귀함수와 짝꿍이다. 그리고 함수를 돌 때마다, 방문여부(visited, check)를 확인하기 위한 변수를 자주 사용한다.

 

코드의 전체 구조

* 코드 구조

코드의 전체구조에는 크게 DFS 선언부와 main 호출부가 있다.

DFS 선언부에는 학생의 id를 입력받아 DFS를 순회했음을 표시하고, 지목된 학생(nextId = graph[id])의 DFS를 호출한다.(재귀)

순회 경로(traced)에 이미 id가 포함이 되어있는 지 확인**하고, 순회한다면 result 결과에 팀이 된 학생들을 추가한다.

 

main호출부에서는 test case의 개수 변수를 입력받고, 각 테스트 케이스마다 DFS를 호출하기 위한 for문을 작성한다.

main의 for문에는 지목된 학생을 받는 graph변수, visit(or check)변수, 케이스의 결과변수 result가 선언된다.

    이후 하위 for문으로 학생마다 DFS를 선회하며, (DFS(id)) 경로를 초기화한다(trace=[]).

 

** 이미 DFS함수를 순회한 학생들을 체크하기 위한 변수 check

(e.g check = [0,0,0,0,0], 학생수 +1의 길이로, 방문한 학생의 인덱스에는 1이 들어간다.)

 

 

 

 

 

import sys
sys.stdin = open('in.txt','rt')

def DFS(id):
    global res
    check[id] = 1
    traced.append(id)
    nextId = graph[id]
    if check[nextId] == 0:
        DFS(nextId)
    else:
        if nextId in traced:
            res += traced[traced.index(nextId):]
        return


c = int(input())
for _ in range(c):
    s = int(input())
    graph = [0] + list(map(int, input().split()))
    check = [0]*(s+1)
    res = []
    for i in range(1,s+1):
        if check[i] == 0:
            traced = []
            DFS(i)

    print(s-len(res))

 

---

 

 * 추가  

 sys.setrecursionlimit(10**7) 

 

자꾸만 런타임에러가 나서 sys.setrecursionlimit(10**7)을 맨 첫줄에 추가했다.

setrecursionlimit은 재귀함수를 사용할 때 필수로 들어가는 조건사항인데, 말인 즉슨 파이썬의 재귀 깊이 제한이 default 1000으로 되어 있는 것을 더 깊게 까지 탐색할 수 있도록 한계를 늘려서 조정한다는 뜻이다.

 

 

 

* 참고

https://deep-learning-study.tistory.com/583

https://velog.io/@ohdowon064/Python-sys.setrecursionlimithttps://velog.io/@ohdowon064/Python-sys.setrecursionlimit

https://fuzzysound.github.io/sys-setrecursionlimit