[백준] 2668 숫자고르기 Python

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

2668번: 숫자고르기

 

1. 유형 : DFS 

2. 문제 아이디어 

1	2	3	4	5	6	7
3	1	1	5	5	4	6

입력되는 노드를 시작점이라고 보고 인덱스들이 이어지는 노드라고 생각하여 그래프를 그리면 다음과 같다. 

1: [2, 3]
2: []
3: [1]
4: [6]
5: [4, 5]
6: [7]
7: []

그래프를 dfs로 순회한다. 
방문한 노드를 visited 리스트에 표시하여 이미 방문한 노드는 재방문하지 않도록 한다. 
dfs 인자로 문제에서 구하는 집합을 구한다. 

node를 탐색하고, 현재 node와 연결된 인접 노드들을 방문한다. 
방문하지 않았다면 dfs를 재귀 호출한다
방문을 이미 해서 route 에 원소가 들어있다면 이는 사이클을 의미하는 것이므로 재귀함수 탈출 조건이 된다. 

# 2668
n = int(input())
graph = [[] for _ in range(n+1)]

for a in range(n):
    b = int(input())
    graph[b].append(a+1) # index는 0부터이므로

visited = [False] * (n+1) # 노드 방문 여부 확인

result = [] # 결과 집합
# route 는 집합
def dfs(node, route):
    route.add(node)
    visited[node] = True
    for i in graph[node]:
        if i not in route: # 방문하지 않았다면
            dfs(i, route.copy()) # copy 는 얉은 복사 -> 참조만 복사한 복사이다 즉 원래 route와 동일한 주소를 가리킴 
        else:# 이미 node가 route에 포함되어있으므로 사이클이 생기는 경우 
            result.extend(list(route)) # append 대신 extend를 써야 동일 배열에 이어서 추가가 된다. 
            return

for i in range(1, n+1):
    if not visited[i]:
        dfs(i, set([]))
result.sort()
# 정수들의 개수 출력하기
print(len(result))
# 뽑힌 정수들을 오름차순으로 출력하기
for i in result:
    print(i)