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

 

9466번: 텀 프로젝트

풀이

처음에 사이클 체크를 어떻게 해야 하는지 엄청 고민했다...
결국 구글링하여 솔루션들을 참고했다 ㅠ
내가 시도하려는 풀이에선 방문체크 배열이 두 개가 필요함을 알 수 있었다.

• 방문 체크를 할 배열, 완전히 방문이 끝났음을 알리는 배열 두 개의 visited를 확인할 배열이 필요
• visited[n] = false: 아직 방문안한 곳이므로 DFS 다음 탐색 node는 n
• visited[n] = true & finished[n] = false
  • 방문은 했으나 완전히 방문이 끝나지는 않음 == 처음 시작노드로 돌아온 경우이므로 사이클에 해당됨
  • for문을 재귀로 수행하며 사이클에 노드가 몇 개 있는지 cnt에 저장
• 마지막에 전체 노드 개수 - cnt를 해주면 정답

---

코드

import java.io.*;
import java.util.*;

public class Main {
static int T, n, cnt;
static final int SIZE = 100010;
static int[] arr;
static boolean[] visited, finished;

public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
StringTokenizer st;

T = Integer.parseInt(br.readLine());

while(T-- > 0) {
n = Integer.parseInt(br.readLine());
cnt = 0;
arr = new int[SIZE];
visited = new boolean[SIZE];
finished = new boolean[SIZE];
st = new StringTokenizer(br.readLine());

for (int i = 1; i <= n; i++)
arr[i] = Integer.parseInt(st.nextToken());

for (int i = 1; i <= n; i++)
if (!visited[i]) explore(i);


bw.write((n - cnt) + "\n");
}
br.close();
bw.close();
}

public static void explore(int n) {
visited[n] = true;

int next = arr[n];

if (!visited[next]) explore(next);
else if (!finished[next]) {
for (int i = next; i != n; i = arr[i]) cnt++;
cnt++;
}
finished[n] = true;
}

}