[python] 백준 2668 숫자고르기

https://www.acmicpc.net/problem/2668

2668번: 숫자고르기

문제 해결

•  사이클을 만들어서 사이클에 속해 있는 원소를 모두 가져올 수 있는지 확인하는 문제
•  사이클에 들어가는지 확인은 bfs, dfs 모두 가능하다.(하지만 문제에서 dfs를 원하는것 같다.)
•  이전에 풀어봤던 문제와 비슷하다.(무슨 문제였는지는 까먹어서...ㅜㅜ)

 

CODE

def cycle(num):
    global visited, c,result
    c.append(num)
    nx = graph[num]
    if not visited[nx]:
        visited[nx] = True
        cycle(nx)
    else:
        if nx in c:
            first = c.index(nx)
            for s in c[first:]:
                result.append(s)


if __name__=='__main__':
    n = int(input())
    graph = [0]*(n+1)
    for i in range(1,n+1):
        graph[i] = int(input())
    result = []
    visited = [False]*(n+1)
    for i in range(1,n+1):
        if visited[i] == False:
            c = []
            visited[i] = True
            cycle(i)
    result.sort()
    print(len(result))
    for ans in result:
        print(ans)