반응형
방향 그래프에서 사이클이란 특정 정점에서 시작해 어떠한 경로를 지나 다시 그 정점으로 돌아오는 경로를 말합니다. 무방향 그래프에서는 서로소 집합으로 사이클을 판별할 수 있습니다. 반면, 방향 그래프에서는 어떻게 사이클이 있는지 판별할까요?
DFS는 깊이우선탐색입니다. DFS를 이용해 그래프를 탐색하게 되면 해당 시작 정점에서 갈 수 있는 모든 정점을 방문한 뒤 종료됩니다. 이를 이용해 시작점과 방문점으로 이루어진 DFS 함수를 구성하여 시작점과 방문점이 같은 경우 사이클이 존재한다고 판단할 수 있습니다.
다음 그래프는 4,6,7 노드 간 사이클이 존재합니다. 이 그래프에 대해 사이클이 존재하는지에 대한 코드는 다음과 같습니다.
시간 복잡도
일단 DFS를 수행하는 것은 모든 정점을 방문하고 모든 간선을 방문하니 정점의 개수와 간선의 개수를 합한 $O(V+E)$가 소요됩니다. 사이클을 찾기 위해 모든 정점에 대해 DFS를 수행하면 $O(V(V+E))$가 소요되게 됩니다.
그렇다면, 모든 정점에 대해 사이클을 찾지 않고 한 번의 DFS로 사이클을 찾아 $O(V+E)$만큼 걸리게 할 수 없을까요? 다시 한번 DFS의 정의를 생각해보면 DFS를 수행하다가 재귀 탐색이 종료되지 않았는데, 다시 방문하게 된다면 사이클이 있다고 판단할 수 있습니다. 즉, 사이클이 존재하는 노드와 연결된 노드로부터 사이클 존재여부를 바로 확인할 수 있습니다.
참조
반응형
'Computer > Coding Test' 카테고리의 다른 글
| 코딩테스트 문제 (25) - 텀 프로젝트 (0) | 2021.03.05 |
|---|---|
| 코딩테스트 문제 (24) - 순열 사이클 (0) | 2021.03.05 |
| 코딩테스트 문제 (22) - 랜선 자르기 (0) | 2021.03.05 |
| 코딩테스트 문제 (21) - 가장 긴 팰린드롬 부분문자열 (0) | 2021.03.02 |
| 코딩테스트 문제 (20) - 유효한 팰린드롬 (0) | 2021.03.01 |
