백준_텀 프로젝트_9466

//알고리즘

1. 탐색

 -> 깊이 우선 탐색

 -> n 값이 100,000이므로 시간초과가 안 나도록 풀어야 함.

 

2. 방문배열 이외의 int 배열을 하나 더 사용하여 사이클 생성 시 cnt 값을 구함

 -> 거쳐 온 노드들의 cnt값을 vNum 배열에 저장함

 -> 사이클이 발생 시 해당 cnt값과 vNum에 들어있는 값으로 팀을 이룰 수 있는 사람들의 수를 구함

 -> 거쳐간 노드들의 방문배열은 true로 체크해주고 vNum의 값은 재귀가 끝날 때, 0으로 다시 세팅해줌(백트래킹)

 

3. 결과값 = 노드수(n) - 팀을 이룰 수 있는 사람들의 수(ans)

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class 텀프로젝트_9466 {
	static int T, n, arr[], ans, vNum[];
	static boolean  v[];

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		T = Integer.parseInt(br.readLine());

		for (int tc = 1; tc <= T; tc++) {
			n = Integer.parseInt(br.readLine());
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			arr = new int[n + 1];
			v = new boolean[n + 1];
			vNum = new int[n+1];
			ans = 0;

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

			for (int i = 1; i <= n; i++) {
				if (!v[i]) {
					dfs(i, 1);
				}
			}

			System.out.println(n - ans);

		}

	}

	private static void dfs(int start, int cnt) {
		v[start] = true;
		vNum[start] = cnt;

		if (!v[arr[start]]) {
			dfs(arr[start], cnt + 1);
		} else {
			if (vNum[arr[start]] != 0) {
				ans += (cnt - vNum[arr[start]]+1);
			}
		}
		vNum[start] = 0;
	}
}

 

※ 코드는 짧으나 시간초과를 해결하기위해 2시간이나 걸렸던 문제. 제출도 10번넘게 해서 겨우 해결. 

n값을 보고 시간초과를 예상했으나 구현이 쉽지 않았던 문제.

매번 배열을 생성하려고 했는데 배열생성도 연산에 포함되는줄 몰라서 시간초과가 계속 남. 결국 vNum을 매번 생성하는 코드가 아닌 0으로 초기화 해주는 방식의 백트래킹으로 구현 해서 해결.

방문배열(boolean v)을 true, false로 바꾸는 백트래킹은 많이 해봤지만 이런식의 cnt 값을 초기화 하는 코드는 처음이라 좋은 경험이 되었음.