BaekJoon 9466. 텀 프로젝트 (Java)(DFS)(골드4)

문제출저 : https://www.acmicpc.net/problem/9466

9466번: 텀 프로젝트

문제 조건

- 텀프로젝트를 해야 한다. 학생은 자신을 포함한 단 한명을 선택해서 팀을 꾸릴 수 있다.

- 자세한 설명은 문제 참조.

- 그래프가 cycle을 이뤄야 팀 생성 가능. 답은 팀에 속하지 못한 학생들의 수 이기 때문에

   N - (cycle을 이룬 학생 수) 가 됨.

 

풀이 과정 

 

cycle을 찾아서 그에 해당하는 학생수를 찾으면 된다고 생각.

 

코드 구현

(1) 첫번째 시도

package 백준;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

public class Ex_9466 {
	// 텀 프로젝트(골드4) union-find 문제
	private static boolean[] visited;
	private static Queue<Integer> queue = new LinkedList<Integer>();
	private static int answer = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());
		for (int i = 1; i <= T; i++) {
			int N = Integer.parseInt(br.readLine());

			// 인접 리스트
			int adj[] = new int[N + 1];
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");

			for (int node = 1; node < N + 1; node++) {
				adj[node] = Integer.parseInt(st.nextToken());
			}

			visited = new boolean[N + 1];

			for (int node = 1; node < N + 1; node++) {
				dfs(adj, node, 1);
			}
			// 정답 출력
			bw.write(N - answer + "\n");

			answer = 0;
		}
		bw.flush();
		bw.close();
		br.close();
	}

	private static void dfs(int[] adj, int node, int depth) {
		if (visited[node]) {
			queue.clear();
			return;
		}

		visited[node] = true;

		if (adj[node] == node) {
			answer++;
			queue.clear();
			return;
		}

		if (queue.contains(adj[node])) {
			int temp = queue.poll();
			while (temp != adj[node]) {
				depth--;
				temp = queue.poll();
			}
			answer += depth;
			queue.clear();
			return;
		}

		queue.offer(node);

		dfs(adj, adj[node], depth + 1);

	}
}

 

 cycle을 찾을 때,

   1) 자기 자신을 선택해서 혼자 팀을 이룬경우  

   2) 팀원들이 순환을 이루도록 선택한 경우. -> 이를 확인하기 위해 Queue를 생성하고 학생 수를 샜다.

 

   => 시간초과 !! 큐로 순환을 찾는 것이 비효율 적임을 알게됨.

 

 

(2) 두번째 시도

package 백준;

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

public class Ex_9466_3 {
	// 텀 프로젝트(골드4) union-find 문제
	private static int[] adj;
	private static boolean[] visited;
	private static boolean[] finished;
	private static int answer = 0;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

		int T = Integer.parseInt(br.readLine());
		for (int i = 1; i <= T; i++) {
			int N = Integer.parseInt(br.readLine());

			// 인접 리스트
			adj = new int[N + 1];
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");

			for (int node = 1; node < N + 1; node++) {
				adj[node] = Integer.parseInt(st.nextToken());
			}

			visited = new boolean[N + 1];
			finished = new boolean[N + 1];

			for (int node = 1; node < N + 1; node++) {
				dfs(node);
			}
			// 정답 출력
			bw.write(N - answer + "\n");

			answer = 0;
		}
		bw.flush();
		bw.close();
		br.close();
	}

	private static void dfs(int node) {
		if (visited[node])
			return;
		visited[node] = true;
		int nextNode = adj[node];

		if (visited[nextNode] != true) {
			dfs(nextNode);
		} else {
			if (finished[nextNode] != true) {
				answer++;
				for (int i = nextNode; i != node; i = adj[i]) {
					answer++;
				}
			}
		}
		finished[node] = true;
	}
}

 

두 번째 시도

 

  2개의 배열 필요 

   1) boolean visited[] : 메소드에 처음들어왔든, 혹은 재귀로 불려서 들어왔든 한버니라도 호출된 node인지

                               방문처리를 해주는 배열문

   2) boolean finished[] : visited와 달리, main의 for문으로 dfs를 수행한 노드만을 체킹해주는 배열문

 

  dfs 메소드 살펴보기

private static void dfs(int node) {
		if (visited[node])
			return;
		visited[node] = true;
		int nextNode = adj[node];

		if (!visited[nextNode]) {
			dfs(nextNode);
		} else {
			if (!finished[nextNode]) {
				answer++;
				for (int i = nextNode; i != node; i = adj[i]) {
					answer++;
				}
			}
		}
		finished[node] = true;
	}
}

if(!visited[nextNode]) 부터 보면

다음노드가 방문한 곳이 아니면 dfs재귀로 차례차례 방문한다. 

 

만약 방문한 곳이라면 finished[]배열을 통해서 main for문의 dfs함수를 통해 하나씩 지나간 노드인지 확인한다.

이미 지나간 노드일 경우(finisthed[node]가 true)에는 중북해서 사이클을 카운트할 필요가 없기 때문이다. 

 

지나간 노드가 아닐경우

for문에서 adj[i]로 계속 갱신하면서 첫 노드인 node와 같은 값이 몇번째에 나오는지 카운트 해준다. 

카운트 해준 값이 싸이클을 이루는 노드의 개수 인 것이다.

 

한번의 dfs가 끝나면 끝난 노드의 finished[node]를 true로 체크 해준다. 

 

 

알게된 점

 

Union-Find는 그래프가 완벽한 싸이클을 이루지 않고 연결만 되어 있더라고 사용할 수 있었지만,

이 경우에는 그래프들이 단방향이고 완벽한 싸이클을 이뤘을 때 체크해주어야 한다. 

 

이를 알기 위해서는 2개의 배열

 

visited[]: 방문처리 배열

finished[]: main의 for문에 dfs(node)를 사용했을 떄 들어온 노드 체크처리 배열

 

을 알아야 함을 깨달았다.