
🔗 문제 링크
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)이다.