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

#9466 텀 프로젝트

난이도 : 골드 4

유형 : DP

9466번: 텀 프로젝트

▸ 문제

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

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

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

1	2	3	4	5	6	7
3	1	3	7	3	4	6

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

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

▸ 입력

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

 

▸ 출력

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

 

 

 

문제 풀이  

싸이클을 찾고 싸이클에 해당되지 않는 노드의 수를 구하는 문제이다. 처음에 간단하게 BFS탐색으로 싸이클을 찾고 싸이클에 해당되지 않은 노드들의 갯수를 카운트하여 출력했지만 시간초과가 떴다. 간단한 문제인줄 알고 조건을 대충보고 넘긴게 잘못이었다. 그래서 DFS탐색으로 푸니 쉽게 해결되었다.

 

📚 조건

  ∙ 학생의 수 n (2<= n <= 100,000)

  

학생의 수를 보니 최대 10만이었다. 해당 그래프는 단방향 탐색으로 BFS로 탐색하면 일단 N개의 노드를 조회하고 해당 노드의 최악의 경우 N번을 순회해야한다. 그래서 O(10^5 * 10^5)가 될 수도 있기 때문에 시간초과가 발생한다. (union-find도 마찬가지로 탐색시간이 너무 많이 걸린다.)

---

시간초과 BFS, Union-find 코드 보기↓

BFS 코드 ✖︎ 

public class Main {

	public static void main(String[] args) throws IOException{
    
		// 생략 ...
    
		int cnt=0;
		for(int i=1; i<n+1; i++) {
			check = new boolean[n+1];
			if(bfs(i) ==0) {
				cnt++;
			}
		}
		System.out.println(cnt);
        
        
	}
	static int bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		
		check[start] = true;
		q.add(start);
		
		while(!q.isEmpty()) {
			int pos = q.poll();
			
			for(int next : list[pos]) {
				if(start == next) {
					return 1;
				}
				if(!check[next]) {
					check[next] = true;
					q.add(next);
				}
			}
		}
		return 0;
	}
}

 

✖︎ BFS 싸이클 체크한 코드

BFS로 이미 방문한 싸이클을 재방문하지 않으려고 할 수는 있지만 그래도 최악의 경우 1->2, 2->3 ,... , N->1인 경우 N개의 노드 N번 순회하므로 시간초과가 발생한다. 그리고 되추적 코드도 그렇게 이쁘지 않다.

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

public class Main {
	public static void main(String[] args) throws IOException{
    
		//생략
        cnt=0;
        for(int i=1; i<n+1; i++) {
        	if(!cycle[i]) {
		        check = new boolean[n+1];
		        bfs(i);
        	}
        }
		System.out.println(n-cnt);
		
	}
	static void bfs(int start) {
		Queue<Integer> q = new LinkedList<>();
		check[start] = true;
		q.add(start);
		
		while(!q.isEmpty()) {
			int pos = q.poll();
			int next = link[pos];
			if(start == next) {
				cnt++;
				next = link[next];
				cycle[next]=true;
				while(next != start) {
					cnt++;
					next = link[next];	
					cycle[next]=true;
				}
				return;
			}
			if(!check[next]) {
				check[next] = true;
				q.add(next);
			}
		}
	}
}

 

+ Union-find로는 싸이클 탐색까지는 간단하게 구하지만 싸이클에 해당되는 노드를 카운트를 하는 과정에서 꽤나 많은 시간이 소요되는 듯 하다.  

✖︎Union-find 코드

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

public class Main {

	static int n, cnt;
	static int[] parents,link;
	static boolean[] check,cycle;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int t = Integer.parseInt(br.readLine());
		
		for(int test=0; test<t; test++) {
			n = Integer.parseInt(br.readLine());
			parents = new int[n+1];
			link = new int[n+1];
			for(int i=1; i<n+1; i++) {
				parents[i] = i;
			}
			check = new boolean[n+1];
			cycle = new boolean[n+1];
			
			st = new StringTokenizer(br.readLine());
			cnt = 0;
			for(int i=1; i<n+1; i++) {
				int from = i;
				int to = Integer.parseInt(st.nextToken());
				
				link[to] = from;
				union(from, to);
			}
			
			
			System.out.println(n-cnt);
		}
		
	}
	static int find(int x) {
		if(parents[x] == x) return x;
		
		int rx = find(parents[x]);
		return rx;
	}
	
	static void union(int from, int to) {
		int x = find(from);
		int y = find(to);
		
		if(x==y) {
			int next = link[to];
			cnt++;
			while(next != to) {
				cnt++;
				next = link[next];
			}
			
		}
		else {
			parents[x] = y;
		}
		
	}
}

 

 

---

 

그래서 DFS탐색을 사용했다. 이렇게 크기가 큰 그래프이고 모든 노드를 조회하는 경우에는 BFS보다 DFS를 사용하는 것이 좋다. DFS는 일단 Stack방식으로 노드를 조회하기 때문에 탐색 노드 종료를 쉽게 체크할 수 있다.

(제일 먼저 방문한 노드의 함수는 깊이 탐색이 모두 끝나고 가장 마지막으로 종료되기 때문)

 

싸이클을 찾기 위해서는 방문여부를 두가지 방법으로 해야 한다.

 

첫 번째 배열 check[] 로는 해당 노드 방문 여부를 체크하고

 

두 번째 배열 isSearchEnd[] 로는 해당 방문 노드 탐색 종료 여부를 체크해줘야 한다.

  → 만약 isSearchEnd= false; 탐색이 종료되지 않았는데 방문이 된다면 그 노드는 싸이클이 있는 노드이므로 간주하고 카운트를 해주면 된다.

  → 그리고 해당 노드의 꼬리를 쫓아가서 싸이클에 해당되는 모든 노드를 카운트하면 된다.

while(next != pos) {
	cnt++;
	next = link[next];
}

 

풀이 코드 

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

public class Main {

	static int n, cnt;
	static int[] link;
	static boolean[] check, isSearchEnd;
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		int t = Integer.parseInt(br.readLine());
		
		for(int test=0; test<t; test++) {
			n = Integer.parseInt(br.readLine());
			link = new int[n+1];
			check = new boolean[n+1];
			isSearchEnd = new boolean[n+1];
			
			st = new StringTokenizer(br.readLine());
			for(int i=1; i<n+1; i++) {
				int from = i;
				int to = Integer.parseInt(st.nextToken());
				
				link[from]=to;
			}
			cnt =0;
			for(int i=1; i<n+1; i++) {
				dfs(i);
			}
			System.out.println(n-cnt);
		}
		
	}
	static void dfs(int pos) {
		check[pos] = true;
		int next = link[pos];
		if(!check[next]) {
			dfs(next);
		}else {
			if(!isSearchEnd[next]) {
				cnt++;
				while(next != pos) {
					cnt++;
					next = link[next];
				}
			}
		}
		isSearchEnd[pos] = true; 
	}
}

 

연습삼아 내가 아는 모든 방법을 다 써봐서 해봤지만 모두 시간초과로 운은 작용하지 않았다.

 

가벼운 데이터를 다룰 때는 위의 방법은 모두 통과할테지만 역시 데이터의 크기가 증가할수록 최적화된 알고리즘을 선택하는게 얼마나 중요한지 다시금 깨달았다.

 

구현만 할 줄 알지 어디에 쓰이는지도 모른다면 무엇을 코드해도 운에만 의지하게 될 것이다. 항상 이 알고리즘이 왜 생겼고 어떻게 쓰이는지 생각하면서 사용하자~