[백준] 2668 숫자고르기

🔗 문제 링크

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

💻 코드

import sys
input = sys.stdin.readline 

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

for i in range(1,n+1):
    numbers[i] = (int(input()))
# n^3도 가능, DFS
# i+1과 자기자신이 같은 경우
result = []

def dfs(start):    

    visited[start] = 1
    cycle_idx.append(start)
    cycle_set.append(numbers[start]) # [idx,원소]
    
    if not visited[numbers[start]]:
        dfs(numbers[start])
        

for i in range(1,n+1):
    visited = [0] * (n+1)
    cycle_idx = []
    cycle_set = []
    dfs(i)

    if len(cycle_set) == 1 and cycle_set[0] == cycle_idx[0]:
        result.append(cycle_set[0])
        
    elif set(cycle_idx) == set(cycle_set):
        for i in cycle_set:
            result.append(i)
            
    
result = set(result)
print(len(result))
for i in sorted(result): # set-> result로 변환됨 
    print(i)

🤷‍♂ 풀이

• DFS를 이용해 사이클을 탐색하면 된다.

• 이 때 cycle_set == cycle_idx여야 한다.

• 처음에는 4 3 2 1 예제를 고려하지 못해 틀렸다.

• dfs를 1부터 n+1까지 계속 돌아야하므로 방문 리스트를 항상 초기화해줘야한다.

• dfs에서 한 숫자가 최대 1번씩 방문되지만 전체 탐색에 for 루프를 사용하기에 시간복잡도는 O(n^2)이다.