1. 꼬리 잡기 문제(주기 문제)
2. end를 잡았을 때 idx set과 val set이 같은지 확인하고 같으면 최종 result set에 삽입한다.
3. end가 잡히고 idx-set과 val-set이 같지 않은 경우 이는 오류 사례이므로 false를 반환하여 함수를 종료합니다.
4. 끝이 잡히지 않는 상황에서 재귀적으로 dfs 함수를 호출한다.
5. main 함수에서 결과 집합에 대상 요소가 없으면 요소의 dfs 함수가 호출됩니다.
*별표를 사용하여 최종 결과 값을 반환합니다.
구분 기호로 ‘\n’을 사용하십시오. 분리
import sys
sys.setrecursionlimit(1000000)
n = int(input())
arr = (0) #0번 idx에 0 val 넣어주기
result = set(())
for _ in range(n):
arr.append(int(input()))
def dfs(top, bottom, start):#idx집합, val 집합, 시작포인트
top.add(start)
bottom.add(arr(start))
if arr(start) in top: #꼬리잡기 성공
if top == bottom:
result.update(top)
return True
return False #꼬리 잡기 성공했는데 위 아래 다르면 False
#꼬리 잡기 실패
return dfs(top,bottom,arr(start))
for i in range(1,n+1):
if i not in result:
dfs(set(),set(),i)
print(len(result))
print(*sorted(list(result)), sep='\n')
(BOJ) 선발번호 2668 백준 (Python)
백준 2668 Picking Numbers (Gold 5) Solving Python, DFS, Graph
velog.io