문제
N명의 학생이 각각 한 명을 선택한다. 선택이 순환을 이루는 그룹이 팀이 된다. 팀에 속하지 못하는 학생 수를 구하라.
입력
테스트 케이스 수 T, 각각 N과 N명의 선택이 주어진다.
출력
각 테스트 케이스에 대해 팀에 속하지 못한 학생 수를 출력한다.
예제
| 입력 | 출력 |
|---|---|
1 7 3 1 3 7 3 4 6 | 3 |
풀이
DFS로 함수형 그래프에서 사이클을 찾아 팀 멤버를 센다.
- 각 노드에서 DFS를 시작한다 (이미 방문했으면 스킵)
- 다음 노드가 미방문이면 재귀 탐색한다
- 다음 노드가 방문했지만 아직 확정(check)되지 않았으면 사이클 발견이다
- 사이클 내의 노드 수를 cnt에 더한다 (다음 노드부터 현재까지 순회)
- 탐색 종료 시
check[cur] = true로 확정한다 N - cnt가 팀에 속하지 못한 학생 수이다
핵심 아이디어: 각 노드가 정확히 하나의 간선을 가지는 함수형 그래프에서, visit/check 두 배열로 사이클을 감지한다. visit은 현재 탐색 경로, check는 확정 여부를 나타낸다.
코드
package day449;
import java.util.*;
import java.io.*;
public class Day402BOJ9466텀프로젝트 {
static int T, N, cnt;
static int[] arr;
static boolean[] visit, check;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringBuilder sb = new StringBuilder();
StringTokenizer st = null;
T = Integer.parseInt(br.readLine());
for (int tc = 0; tc < T; tc++) {
N = Integer.parseInt(br.readLine());
arr = new int[N + 1];
visit = new boolean[N + 1];
check = new boolean[N + 1];
cnt = 0;
st = new StringTokenizer(br.readLine());
for (int i = 1; i < N + 1; i++)
arr[i] = Integer.parseInt(st.nextToken());
for (int i = 1; i < N + 1; i++)
dfs(i);
sb.append(N - cnt).append("\n");
}
System.out.println(sb);
br.close();
}
static void dfs(int cur) {
if (visit[cur])
return;
visit[cur] = true;
int next = arr[cur];
if (!visit[next])
dfs(next);
else {
if (!check[next]) {
cnt++;
for (int i = next; i != cur; i = arr[i])
cnt++;
}
}
check[cur] = true;
}
}복잡도
- 시간: O(N) - 각 노드를 최대 한 번 방문
- 공간: O(N) - visit, check 배열