사용한 것
- 조건을 만족하는 경우만 계산하기 위하여
Stack
으로 구현한 백트래킹 사용
- 그래프의 순환을 판별하기 위한
visited
, finished
풀이 방법
- 팀을 이룬다는 것 -> 순환한다는 것
- 순환하는 정점의 개수인
numOfCircle
을 0으로 생성
- for문을 돌며 index 0 부터의 정점을 시작으로 단방향으로 계속하여 이동
- 방문한 정점은
visited
를 true로 변환하고 스택에 넣어줌
- 방문한 정점을 다시 방문하는 경우 2 가지로 나뉨
finished
가 false인 경우 처음 다루는 정점
idx
까지가 순환이므로 계속 numOfCircle
++ 해줌
- 스택의 나머지 부분은 순환 부분이 아니므로
finished
만 true로 변경
finished
가 true인 경우 이미 다룬 정점
- 스택에 저장된 것들이 있으면 모두
finished
를 true로 변경
- 전체 길이에서
numOfCircle
을 뺀 값을 출력
코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Stack;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
int[][] infos = new int[N][];
for (int i = 0; i < N; i++) {
br.readLine();
infos[i] = Arrays.stream(br.readLine().split(" "))
.mapToInt(Integer::parseInt)
.toArray();
}
for (int i = 0; i < N; i++) {
System.out.println(findNumOfNotCircle(infos[i]));
}
}
public static int findNumOfNotCircle(int[] info) {
boolean[] visited = new boolean[info.length];
boolean[] finished = new boolean[info.length];
int numOfCircle = 0;
for (int i = 0; i < info.length; i++) {
if (visited[i]) {
continue;
}
Stack<Integer> stack = new Stack<>();
int idx = i;
while (true) {
if (visited[idx]) {
if (!finished[idx]) {
while (true) {
int popped = stack.pop();
finished[popped] = true;
numOfCircle++;
if (popped == idx) {
break;
}
}
}
while (!stack.isEmpty()) {
int popped = stack.pop();
finished[popped] = true;
}
break;
}
visited[idx] = true;
stack.push(idx);
idx = info[idx] - 1;
}
}
return info.length - numOfCircle;
}
}