안 쓰던 블로그

그래프에서 사이클 구간 찾는 문제 문제 이해 자체는 쉬운데 구현이 어려웠다 사이클을 찾아야 하는데, 다른 사람들 글을 보니까 finish배열을 써서 finish가 체크가 아닌데 visit는 체크이면 사이클이고 그런다던데 뭔소린지 직관적으로 이해되지 않아서 이해하는 데 좀 걸렸다 1. 사이클 확인 그래서 내 나름대로 이해해 보았는데, finish배열말고 아래처럼 생각하면 좋더라 void dfs(int now) { int next = v[now]; //가리키는 거 if (visit[next]) { //방문을 했던 노드인데 또 탐색하러 오게 되면 사이클이다 //구현 } visit[now] = 1; dfs(next); //다음 경로 } dfs를 돌면서 보통 이렇게 방문을 체크하고, 방문하지 않았으면 dfs를 또..