백준 2668 숫자고르기 Python

🐸 문제 정보

2668번: 숫자고르기

 

🤖 알고리즘

DFS

 

⏱️ 풀이 시간

38.36m

 

📝 풀이

cycle을 찾으면 되는 문제인 것은 알겠으나...

구현하는 것이 생각보다 어려웠던 문제였다ㅠㅠ

 

DFS로 푸는데, 이번에 확인할 노드를 인자로 전달 받아서,

시작했던 노드와 다시 만나면 res에 해당 노드를 넣어주는 방식으로 풀었다.

 

🧑‍💻 나의 답

# pypy3

import sys
input = sys.stdin.readline

n = int(input().rstrip())
graph = [0] + [int(input().rstrip()) for _ in range(n)]
res = []

def dfs(cur):
    global start
    visited[cur] = True
    next = graph[cur]
    if not visited[next]:
        dfs(next)
    elif visited[next] and (next == start):
        res.append(next)
        return

for i in range(1, n + 1):
    visited = [False] * (n + 1)
    start = i
    dfs(i)

print(len(res))
print(*sorted(res), sep='\n')