[BOJ] 2668 - 숫자고르기 (Python)

 

 

아이디어

 

둘째 줄의 숫자를 인덱스로 하여 탐색해나갈 때 탐색을 시작한 인덱스로 되돌아오면 방문한 숫자들은 조건을 만족한다.

 

 

풀이

 

import sys

input = sys.stdin.readline

def solution():
    N = int(input())
    numbers = [0]+[int(input()) for _ in range(N)]
    visited = [0]*(N+1)
    for i in range(1, N+1):
        if visited[i] == 0:
            _visited = [0]*(N+1)
            _visited[numbers[i]] = 1
            queue = [numbers[i]]
            j = 0
            cnt = 1
            while j < cnt:
                idx = queue[j]
                j += 1
                if _visited[numbers[idx]] == 0:
                    _visited[numbers[idx]] = 1
                    queue.append(numbers[idx])
                    cnt += 1
            if queue[-1] == i:
                for num in queue:
                    visited[num] = 1
    print(sum(visited))
    for i in range(1, N+1):
        if visited[i]:
            print(i)

solution()