BOJ 2668: 숫자고르기 [Python 3]

생각보다 너무 어려웠던 DFS 문제이다.

DFS알고리즘은 계속 배워도 쉽지않은 것 같다.

저번에 풀었던 https://www.acmicpc.net/problem/9466 

9466번: 텀 프로젝트

이 문제와 유사한 것 같다.

 

코드는 다음과 같다.

import sys
input=sys.stdin.readline
def dfs(v,i):
    visited[v]=True
    w=data[v]
    if not visited[w]:
        dfs(w,i)
    elif visited[w] and w==i:
        result.append(w)
n=int(input())
data=[0]+[int(input()) for _ in range(n)]
result=[]
for i in range(1,n+1):
    visited=[False]*(n+1)
    dfs(i,i)
print(len(result))
result.sort()
for i in result:
    print(i)

DFS 함수부터 보자. 

v는 현재 좌표, i는 시작한 좌표이다. 

좌표들을 돌면서, 만약 와본적이 없는 좌표이면, 와봤다고 체크하고 다음 행선지로 보내고,

만약 이미 도착했었던 좌표라면, 

이미 와본적이 있었는지 확인한다.

 

이를 모든 좌표마다 체크해주면서, 풀어준다.