[GeeksForGeeks] Detect cycle using DFS

 

 

🔒 문제

양방향 그래프에서 사이클이 존재하는지 여부를 반환하는 함수를 작성하는 문제이다.

 

Detect cycle in an undirected graph | Practice | GeeksforGeeks

💭 생각의 흐름

일단 문제 자체에서 DFS를 사용하여 사이클을 탐색하라고 했다.

정석적인 DFS recursive function을 작성하고 사이클 생기는 시점에 true만 리턴하면 된다고 생각했다.

Q. 사이클이 생기는 시점이 언제인가?
A. BackEdge (부모노드 이외의 노드에 연결되는 선이 발견되는 시점)

 

따라서 visited (방문 기록) 배열을 두고

visited 상에 방문된 상태로 기록되있으면서 parent 노드가 아닌 노드로 연결되있을 경우 바로 true (사이클이 존재)를 리턴하도록 한다.

 

⚠️ 실수

아래 그림 처럼 그래프가 2개 이상 주어질 수도 있다.

문제를 끝까지 읽어보면 다수의 그래프를 input으로 주고 1개라도 사이클이 존재하면 true를 리턴하도록 요구한다.

visited 상에 방문된 상태로 기록되있으면서 parent 노드가 아닌 노드로 연결되있을 경우 바로 true (사이클이 존재)를 리턴하도록 한다.
=> 이 방식이 틀린것은 아니나 하나라도 true를 리턴한다면 나머지 시점엔 더이상 DFS 탐색을 할 필요가 없다.
따라서 sub graph DFS loop 상에서 하나라도 true가 식별될 때 return true하도록 코드를 개선해야한다.
모든 노드에 대해 탐색을 시도했다가 시간 초과를 맞았다 ㅡㅗㅡ.

 

🔑 풀이