[백준] 2668 숫자고르기 / dfs / python 골5

첫째 줄 숫자를 노드로

둘째 줄 숫자를 노드와 연결된 숫자로 생각하면

그래프 간선이라고 생각할 수 있다

 

입력받을 때 방향성 그래프 형태로 구성한다

 

뽑힌 숫자들이 이루는 집합, 숫자들이 가리키는 숫자들이 이루는 집합

이 두 개가 동일하려면 집합 내 숫자들은 사이클을 형성해야 한다

최대 사이클을 찾는 문제로 해석할 수 있다

 

그래프를 돌면서 현재 원소를 방문한 적이 없으면 dfs함수를 돌린다

해당 원소가 시작점이 되기 때문에, 해당 원소와 빈 배열을 dfs 함수로 넘겨준다

 

dfs 함수

만약 현재 node가 이미 방문된 경우

현재까지 누적된 경로에 node값이 존재한다면 사이클임

path에서 사이클에 해당하는 부분을 잘라 result 집합에 추가한다

 

현재 node를 방문 처리한다

현재 node를 path에 추가한다

현재 node가 가리키는 원소를 node값으로 하여 dfs를 호출한다 dfs(graph[node], path)

 

이 과정까지 마치면 현재 node는 탐색이 끝났으므로 pop해서 지운다

 

n = int(input())
graph = [0]*(n+1)

for i in range(1,n+1):
    graph[i] = int(input())

visited=[False]*(n+1)


def cycle(graph,n):
    result=set()
    def dfs(node,path):
        if visited[node]:
            if node in path:
                result.update(path[path.index(node):])
            return
        visited[node]=True
        path.append(node)
        dfs(graph[node],path)
        path.pop()
    for i in range(1,n+1):
        if not visited[i]:
            dfs(i,[])
    return sorted(result)

result = cycle(graph,n)
print(len(result))

print("\n".join(map(str,result)))