[ 그래프 이론-2668 ] 숫자고르기(Python)

 

---

접근법

어려웠다..

단순히 dfs 측면으로 접근하고자 했는데 " 1->3->2->3" 과 같이 일치하지 않는 집합을 거름과 동시에 중간에 일치하는 집합을 찾아내는 아이디어를 도출하는게 매우 힘들었다...

---

정답

import sys
sys.setrecursionlimit(10**6)

N = int(input())

graph = [[] for _ in range(N+1)]

for i in range(1,N+1):
    graph[int(input())].append(i)
visited = [0]*(N+1)

result = set()

def dfs(i, arr):
    for j in graph[i]:
        if visited[j]:
            while arr:
                tmp = arr.pop()
                result.add(tmp)
                if j == tmp:
                    break
            return
        
        visited[j] = 1
        dfs(j, arr+[j])
        visited[j] = 0
            
for i in range(1,N+1):
    dfs(i,[])
    
ans = sorted(list(result))
print(len(ans),*ans,sep='\n')

 

솔직히 아직 완벽하게 이해가 안되서...나중에 재업로드 하겠다ㅠㅜ