[백준/BOJ] - 2668번 python 풀이 - DFS

 

---

1. 꼬리잡기 문제이다.(사이클 문제)

2. 꼬리를 잡았을 경우 idx 집합과 val 집합이 동일한지 여부를 확인하여 해당할 경우 최종 결과 집합에 넣어준다.

3. 꼬리를 잡았는데 idx 집합과 val 집합이 동일하지 않으면 실패한 경우이므로 False를 반환하여 함수를 탈출한다.

4. 꼬리를 잡지 못한 상황에선 재귀적으로 dfs 함수를 호출한다.

5. 메인 함수 쪽에서는 result 집합에 target element가 없을 경우 해당 element의 dfs 함수를 호출한다.

 

*아스테리크를 활용하여 최종 결과 값을 출력한다. 구분자는 '\n'을 사용한다. separate

---

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')

---

참조: https://velog.io/@deannn/BOJ-%EB%B0%B1%EC%A4%80-2668%EB%B2%88-%EC%88%AB%EC%9E%90%EA%B3%A0%EB%A5%B4%EA%B8%B0-Python

[BOJ] 백준 2668번 숫자고르기 (Python)