백준 9466번. 텀 프로젝트 (Java)

문제 링크 : https://www.acmicpc.net/problem/9466

싸이클을 형성하지 못하는 노드 갯수를 찾는 문제입니다.

일반적인 DFS로 모든 노드를 탐색하면 시간 초과가 납니다.

테스트케이스가

2 3 4 5 1

이렇게 주어졌을 때 모든 DFS를 탐색한다면

1->2->3->4->5

2->3->4->5->1

3->4->5->1->2

4->5->1->2->3

5->1->2->3->4

O(n^2)의 시간복잡도를 갖게 되고, 최대 10만의 n 값으로 탐색한다면 시간 초과가 날 수밖에 없습니다.

따라서 이 문제의 핵심은 더이상 방문할 필요가 없는 노드를 구분해서 쓸데없는 탐색을 막는 것입니다.

그렇다면 어떻게 구분 할 것인가?

일단 이 문제는 모든 노드들은 무조건 다른 노드 한개를 가리킨다라는 조건이 있습니다.

이 말은 DFS 탐색이 끝나기 위해선 무조건 싸이클에 들어가야 한다는 뜻입니다.

예제 테스트케이스를 봐도

1->3->3

2->1->3->3

3->3

어디서 시작해도 끝은 항상 싸이클입니다.

이 점을 이용한다면 1, 2, 3 번 노드를 모두 탐색 할 필요 없이 1번 노드 탐색만으로도 싸이클을 만난다는 사실을 알 수 있습니다.

그렇다면 2번과 3번 노드는 끝까지 탐색할 필요가 없게 됩니다.

2번 노드를 탐색해서 1번 노드를 찾아 들어간다면 1번에서 탐색한 결과와 똑같이 나오기 때문에 이를 방지하여 중복을 최소화 합니다.

그래서 기본적으로 DFS 탐색에 사용되는 visited 배열 외에 finished 배열을 하나 더 만들어줍니다.

visited 배열은 단순히 방문 여부를 체크하는 것이고, finished 배열은 방문한 노드에서 싸이클을 이미 뽑아냈었는가를 확인합니다.

1->3->3

1번 노드 탐색을 할 때는 visited[3] 값이 true기 때문에 탐색이 끝납니다.

탐색의 끝은 항상 싸이클이기 때문에 3번 노드는 무조건 싸이클을 형성하는 노드 중 하나라는 사실을 알 수 있습니다.

그럼 3번 노드부터 연결된 노드를 탐색하는 for문을 통해 3번 노드와 싸이클을 이루는 노드 갯수를 카운트합니다.

이 작업이 끝나면 1번과 3번 노드는 더이상 사용할 필요가 없기 때문에 finished 값을 true로 바꿔줍니다.

2->1->3->3

2번 노드 탐색을 할 때는 1번 노드를 만납니다.

하지만 1번 노드는 이미 사용한 노드라 finished 값이 true입니다.

1번 노드와 같은 싸이클을 만날 것이기 때문에 2번 노드는 더이상 탐색을 진행하지 않고 빠져나옵니다.

같은 방식으로 모든 노드를 탐색하면 O(n)의 시간복잡도로 탐색을 끝낼 수 있습니다.