[Java/자바 백준 9466] 텀 프로젝트

풀이

학생이 10만명이므로  O(n^2)으로 풀게되면 시간초과가 나는 문제입니다.

백준 게시판 들어가서 보면 사람들이 엄청나게 고뇌(?)하면서 질문이 엄청 많아요 !

 

저도 엄청나게 고뇌하다고 시간 초과를 해결하지 못했습니다 ㅜㅜ

참고한 예시를 보면서 설명드릴게요 !

 

문제의 포인트는 모든 노드는 다른 노드를 가리킨다 입니다.

즉, DFS를 돌다보면 무조건 싸이클이 생기게 됩니다.

 

ex)

3-2-4-5-6-7-3

 

1부터 dfs 시작하면

1 -> 3 -> 4 -> 5 -> 6 -> 7 -> 3

2 - > 2

3 -> 4 -> 5 -> 6 -> 7 -> 3

 

4 -> 5 -> 6 -> 7 -> 3

5 -> 6 -> 7 -> 3

6 -> 7 -> 3

7 -> 3

 

3,4,5,6,7은 사이클 내에서 반복하는 것을 알 수 있습니다.

 

이 반복을 줄여주는게 핵심입니다.

때문에 처음 dfs(1)을 돌 때 3,4,5,6,7 방문처리를 해주고

dfs(3),dfs(4).... return 해야겠죵 

 

그렇기 때문에 , isFinished 불린 배열을 하나 만들고

dfs 함수 내에서 isSelected 방문하지 않은 값들을 끝까지 탐색을 해줍니다.

 

그렇게 끝 값에 도달하게되면,

마지막에 도달한 값은 무조건 싸이클을 이룬다는 특징을 이용해서

싸이클의 모든 값을 찾아 준 뒤, isFinished에 방문 처리를 합니다.

 

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

public class Main {
	static boolean[] isSelected, isFinished;
	static int[] numbers;
	static int T, N, answer, minus;

	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		for(int testCase = 0 ; testCase < T ; testCase++) {
			N = Integer.parseInt(br.readLine());
			answer = N;
			numbers = new int[N + 1];
			isSelected = new boolean[N + 1];
			isFinished = new boolean[N + 1];
			minus = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			for(int i = 1 ; i <= N ; i++) {
				numbers[i] = Integer.parseInt(st.nextToken());
			}
			
			for(int i = 1 ; i <= N ; i++) {
				dfs(i);
			}
			answer -= minus;
			sb.append(answer).append("\n");
		}
		System.out.println(sb);
	}

	private static void dfs(int now) {
		if(isSelected[now]) return;
		
		isSelected[now] = true;
		int next = numbers[now];
		
		if(isSelected[next] == false) {
			dfs(next);
		}
		else {
			if(isFinished[next] == false) {
				minus ++;
				for(int i = next ; i != now ; i = numbers[i]) {
					minus ++;
				}
			}
		}		
		isFinished[now] = true;
	}
}

 

ps

https://bcp0109.tistory.com/32