[백준/JAVA] 9466_텀 프로젝트

백준🔗

https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

 

 

 

문제

 

 

간단 풀이

DFS를 할 때 방문처리를 하기 위한 boolean배열 하나와 사이클이 형성되는지 여부를 체크하는 boolean 배열을 하나 더 만드는 것이 이 문제의 핵심이라고 할 수 있다.

 

문제에서 학생들의 선택에서 사이클이 발생하게 되면 그 사이클에 포함되는 학생들은 한 팀으로 배정된다.

따라서 모든 경우에 대해 DFS를 수행할 필요 없이, 진행 경로에 사이클이 있음을 알 수 있다면 더이상 탐색을 할 필요가 없고 이를 통해 시간 복잡도를 줄일 수 있다.

 

문제와 조건이 간단했지만 finished 배열을 생각해내고 이해하는 과정이 쉽지 않았던 문제다..😶‍🌫️

 

코드

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

public class Main {
	static int cnt;
	static int[] choice;
	static boolean[] checked, finished;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		int T = Integer.parseInt(br.readLine());
		for (int tc = 1; tc <= T; tc++) {
			int n = Integer.parseInt(br.readLine()); // 학생 수 (2~10만)
			choice = new int[n + 1];
			checked = new boolean[n + 1];
			finished = new boolean[n + 1];
			cnt = 0;
			StringTokenizer st = new StringTokenizer(br.readLine());
			for (int i = 1; i <= n; i++) {
				choice[i] = Integer.parseInt(st.nextToken());
			}
			for (int i = 1; i <= n; i++) {
				if (!finished[i]) {
					findTeam(i);
				}
			}

			System.out.println(n - cnt);
		}
	}

	static void findTeam(int x) {
		checked[x] = true; // 방문처리
		int next = choice[x];
		if (!checked[next])
			findTeam(next);
		if (checked[next] && !finished[next]) { // 사이클이 있다는 것
			cnt++;
			while (next != x) {
				cnt++;
				next = choice[next];
			}
		}
		finished[x] = true; // x를 거쳐 진행하면 사이클이 있음을 표시
	}
}

 

 

참고 자료

[백준] DFS - 9466번 텀 프로젝트 (Java)

 

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