[BOJ] 2668번 숫자고르기

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

2668번: 숫자고르기

# 1

N = int(input())
graph = [-1]
for i in range(1, N+1):
    graph.append(int(input()))
    

res = []

def dfs(v):
    visited[v] = True
    ret = graph[v]
    
    if not visited[graph[v]]:
        ret = dfs(graph[v])
        
    return ret
        
    
        
for i in range(1, N+1):
    visited = [False] * (N+1)
    ret = dfs(i)
    
    if ret == i:
        res.append(i)
        
print(len(res))
print(*res, sep='\n')

 

# 2

N = int(input())
graph = [-1]
for i in range(1, N+1):
    graph.append(int(input()))
    

res = []

def dfs(v, start):
    visited[v] = True
    
    if not visited[graph[v]]:
        dfs(graph[v], start)
    
    if graph[v] == start:
        res.append(start)
        
        
for i in range(1, N+1):
    visited = [False] * (N+1)
    dfs(i, i)
    
print(len(res))
print(*res, sep='\n')

 

여전히 약한 dfs...

다음 노드를 방문하지 않았을 때 다음 노드에 대하여 dfs 수행.

방문했을 경우 조건 확인 (싸이클 형성 여부).