백준 | 9466번 텀 프로젝트 - DFS 문풀

⬛ 백준 9466번 텀 프로젝트 - DFS 문풀

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

9466번: 텀 프로젝트

문제

이번 가을학기에 '문제 해결' 강의를 신청한 학생들은 텀 프로젝트를 수행해야 한다. 프로젝트 팀원 수에는 제한이 없다. 심지어 모든 학생들이 동일한 팀의 팀원인 경우와 같이 한 팀만 있을 수도 있다. 프로젝트 팀을 구성하기 위해, 모든 학생들은 프로젝트를 함께하고 싶은 학생을 선택해야 한다. (단, 단 한 명만 선택할 수 있다.) 혼자 하고 싶어하는 학생은 자기 자신을 선택하는 것도 가능하다.

학생들이(s1, s2, ..., sr)이라 할 때, r=1이고 s1이 s1을 선택하는 경우나, s1이 s2를 선택하고, s2가 s3를 선택하고,..., sr-1이 sr을 선택하고, sr이 s1을 선택하는 경우에만 한 팀이 될 수 있다.

예를 들어, 한 반에 7명의 학생이 있다고 하자. 학생들을 1번부터 7번으로 표현할 때, 선택의 결과는 다음과 같다.

표 그림

위의 결과를 통해 (3)과 (4, 7, 6)이 팀을 이룰 수 있다. 1, 2, 5는 어느 팀에도 속하지 않는다.

주어진 선택의 결과를 보고 어느 프로젝트 팀에도 속하지 않는 학생들의 수를 계산하는 프로그램을 작성하라.

입력

첫째 줄에 테스트 케이스의 개수 T가 주어진다. 각 테스트 케이스의 첫 줄에는 학생의 수가 정수 n (2 ≤ n ≤ 100,000)으로 주어진다. 각 테스트 케이스의 둘째 줄에는 선택된 학생들의 번호가 주어진다. (모든 학생들은 1부터 n까지 번호가 부여된다.)

출력

각 테스트 케이스마다 한 줄에 출력하고, 각 줄에는 프로젝트 팀에 속하지 못한 학생들의 수를 나타내면 된다.

---

💚나의 풀이

• 이 문제는 주어진 그래프에서 DFS로 ‘사이클의 길이’를 구하는 것이 핵심이다.
• 최종적으로 N명에서 전체 사이클 길이를 뺀 값이 ‘팀에 속하지 못한 학생들의 수’가 된다.

매우 헷갈린다. 특히 이 아래의 코드를 이해하는 게 중요하다.

for(int i=nx; i!=now; i=arr[i]) {
		//사이클을 이루는 정점을 계속해서 따라가며 사이클의 길이를 측정합니다. 
		// 시작 정점까지 돌아오면서 count를 증가시킵니다.
		count++;
		//이 코드의 목적은 주어진 그래프에서 사이클의 길이를 찾는 것입니다.
}

now기준으로 nx(다음 방문 정점)이 이미 방문한 정점이라면 (사이클의 길이를 확인해야 한다.)

nx값을 기준으로 arr[nx]값을 계속해서 새로운 i로 갱신해가며 사이클에 포함된 길이를 탐색하는데

사전에 count++을 해둔 이유는 마지막에 i≠now일때까지의 조건을 걸어두었기 때문에 해당 값을 카운팅하지 않으므로 미리 해준 것이다.

풀이 설명

---

💚나의 코드

package to_1228_1;

import java.util.Scanner;

/**
 * 9466번. 텀 프로젝트 - DFS 풀이
 * @author MYLG
 *
 */
public class Main {
	static int TC;
	static int N;
	static int[] arr;
	static boolean[] visited;
	static boolean[] isDone;
	static int count;
	//DFS
	static void DFS(int now) {
		if(visited[now]) return;
		
		visited[now] = true;
		int nx = arr[now];//다음 방문할 정점
		
		if(!visited[nx]) {
			//다음 정점이 이미 방문한 정점 아닌 경우면 더 깊이 탐색한다.
			DFS(nx);
		}else {
			//이미 방문한 정점이라면 사이클을 확인해야 한다.
			if(!isDone[nx]) {
				//만약 아직 끝정점은 아니라면
				count++; //1++
				for(int i=nx; i!=now; i=arr[i]) {
					//사이클을 이루는 정점을 계속해서 따라가며 사이클의 길이를 측정합니다. 
					// 시작 정점까지 돌아오면서 count를 증가시킵니다.
					count++;
					//이 코드의 목적은 주어진 그래프에서 사이클의 길이를 찾는 것입니다.
				}
			}
		}
		
		//모든 작업 끝나면 더 이상 사용 X
		isDone[now] = true;
	}
	
	//실행 메인 
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner kb= new Scanner(System.in);
		
		TC = kb.nextInt();
		for(int t= 0; t<TC; t++) {
			N = kb.nextInt();
			arr = new int[N+1];
			visited = new boolean[N+1];
			isDone = new boolean[N+1];
			count=0;
			
			for(int i=1; i<=N; i++) arr[i]= kb.nextInt();
			
			for(int i=1; i<=N; i++) {
				if(!visited[i]) {
					DFS(i);
				}
			}
			
			System.out.println(N-count);
		}
	}
}