백준

10451번 순열 사이클(DFS, 연결요소)

조주똥 2020. 6. 10. 22:23

#문제링크 : https://www.acmicpc.net/problem/10451

전략 : 하나의 노드로 시작해서 배열의 인덱스와 배열의 값으로 이어진 단방향 그래프를 DFS 탐색한다. 해당 노드의 DFS 탐색이 모두 끝나면, 하나의 싸이클을 탐색한 것이다. 이후에 방문하지 않은 노드를 찾아 같은 행위를 반복하여 싸이클을 찾는다. DFS에서 check배열을 통해 방문한 노드를 체크해주고 다음노드로 넘어간다. DFS의 종료조건은 해당 사이클에서 방문했던 노드를 만나면 return한다. 

Code