BOJ 9466 Term Project

그래프가 주어지면 그래프에서 사이클을 찾고, 사이클에 포함되지 않은 노드의 개수를 출력하는 문제라고 보면된다.

주어지는 그래프가 양방향 그래프가 아닌 단방향 그래프이고, 모든 정점이 서로 연결되어 있지 않을 수도 있다. (그래프 덩어리가 여러개 일 수 있다.)

일단 주어지는 그래프를 자료구조에 저장하는데, 그냥 일차원 배열에 저장 가능하다. 왜냐하면 한 정점은 한 정점만 가르킬 수 있기 때문이다. 그리고 dfs탐색을 하는데, 그러다가 이미 방문했던 정점을 또 방문하려할 때, 사이클이 있다는 것을 알 수 있다. 근데 사이클을 구성하는 정점이 몇 개인지 알아야 한다. 정점을 하나 하나 탐색하면서, 번호를 매긴다. 예를 들어 처음 방문 시작하는 정점은 1, 그 정점에 이어진 정점은 2, 3, 4...이렇게 번호를 매기다가 n번째 정점에서 3번째 정점을 만났다고 하면 n-3+1이 사이클을 구성하는 정점의 개수가 될 것이다.(더 편하게, 사이클에 포함되지 않는 정점의 개수는 n-1개일 것이다) 근데 문제는 방문하지 않은 다른 정점에서 시작해서 이미 방문한 정점과 만났을 때, 사이클이 아닌데 사이클로 판단한다는 것이 문제가 된다. 그래서 배열을 하나 더 만들어서 몇 번 정점에서 시작한 건지를 기록하고 이것을 참고해서 사이클이 아닌 경우를 구별해 보려고 한다.

AC를 받았다. 예전에 푼 코드를 보니 이렇게 비슷하게 푼 것도 있다.