Cycle

🔒 문제 💭 생각의 흐름 문제를 푸는 입장에서 유형을 보지 않을 수가 없는데 조건: 'directed graph' + can connect itself ∴ Union-Find 알고리즘을 사용하기 어렵다. 총 2가지 방식으로 풀이할 수 있겠다. Topological Sort using BFS (Kahn's Algorithm) 풀이 DFS 변형 풀이 여기선 2번 방법을 선택해서 풀이해보겠다. DFS 변형 풀이법의 핵심은 다음과 같다. 전형적인 DFS 코드를 쓰되, 부모 노드 Set(지나온 부모 노드 방문여부)을 Keep 한다! DFS 를 재귀적으로 호출하면서 이전 스택으로 되돌아 가기 직전에 방문처리 되지 않은 상태로 되돌리기 위해 (부모 노드 Set 업데이트) 부모 노드 방문을 취소한다. bool dfsD..

🔒 문제 Detect cycle in an undirected graph | Practice | GeeksforGeeks practice.geeksforgeeks.org 💭 생각의 흐름 일단 문제 자체에서 DFS를 사용하여 사이클을 탐색하라고 했다. 정석적인 DFS recursive function을 작성하고 사이클 생기는 시점에 true만 리턴하면 된다고 생각했다. Q. 사이클이 생기는 시점이 언제인가? A. BackEdge (부모노드 이외의 노드에 연결되는 선이 발견되는 시점) 따라서 visited (방문 기록) 배열을 두고 visited 상에 방문된 상태로 기록되있으면서 parent 노드가 아닌 노드로 연결되있을 경우 바로 true (사이클이 존재)를 리턴하도록 한다. ⚠️ 실수 아래 그림 처럼 그..