[Java Algorithm] 텀 프로젝트 BOJ #9466

문제

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

9466번: 텀 프로젝트

 

내 문제 풀이

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

public class Main {

	static int[] stu;
	static boolean[] cycle, visited;
	static int cnt; // 싸이클에 포함된 학생 수
	
	public static void dfs(int num) {
		if(visited[num]) { // 이미 방문한 경우 (싸이클 !!!)
			cycle[num] = true;
			cnt++;
		} else visited[num] = true; // 첫 방문은 방문 체크
		
		if(!cycle[stu[num]]) dfs(stu[num]); // 다음 노드가 사이클에 포함되지 않았다면 탐색
		cycle[num] = true; // 다음 탐색 시 중복을 피하기 위함
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder out = new StringBuilder();
		
		int tc = Integer.parseInt(in.readLine());
		for(int t = 0; t < tc; t++) {
			int n = Integer.parseInt(in.readLine());
			stu = new int[n];
			visited = new boolean[n];
			cycle = new boolean[n];
			cnt = 0;
			
			st = new StringTokenizer(in.readLine());
			for(int i = 0; i < n; i++) stu[i] = Integer.parseInt(st.nextToken()) - 1;
			for(int i = 0; i < n; i++) if(!cycle[i]) dfs(i); // 싸이클에 포함되지 않은 수면 탐색
			
			out.append((n - cnt) + "\n"); // 전체 학생 수 - 사이클에 포함된 학생 수
		}
		
		System.out.println(out);
	}
}

👉 DFS 문제

 

[ 변수 설명 ]

• boolean[] visited
  방문 체크 (두 번째 방문 시 싸이클임을 판단하기 위함)
• boolean[] cycle
  싸이클 체크 (싸이클에 포함된 학생들을 체크해놓음으로써 중복 탐색을 피하기 위함)
• cnt
  싸이클에 포함된 학생 수 카운트

 

[ 문제 풀이 ]

• 현재 탐색하는 수 num이 visited에서 true일 경우, 이미 방문한 적 있다는 것이고,
  이미 방문한 곳을 또 방문하게 되었다는 것은 싸이클이 이루어졌다는 의미 !!
  => cycle에 true로 표시해주고, cnt를 늘렸다.
• 현재 노드가 가리키는 다음 노드 stu[num]의 cycle이 false라면
  아직 싸이클을 찾지 못한 노드라는 의미이므로, 이어서 탐색할 수 있도록 재귀호출했다.
• 현재 노드의 cycle은 true로 바꿔주어 추후 같은 곳을 중복탐색하는 것을 방지했다.
  
  • 처음에 이 부분 때문에 구현이 어려웠는데, 추가로 설명해보자면
    보통의 그래프 문제에서는 방문 체크를 위해 visited 배열 하나만 사용한다.
  • 하지만 이 문제의 경우, 두 번 방문했을 때가 싸이클을 이루는 것이므로
    한 번 방문한 것을 체크하는 것을 진짜 방문체크라고 볼 수 없는 것이다.
    => visited 배열 하나만으로는 방문 체크에 한계가 있음

 

✔️ 반례 추천

1
3
2 3 2

 

💡 피드백

• 어렵다...... bfs는 꽤 익숙하게 푼다고 생각하는데! dfs는 진짜 너무 어려워....
  이거 재귀를 잘 못해서 그런건가? ㅜㅜ 재귀 문제도 많이 풀어봐야겠다.
• 이 문제는 예외도 꽤 있고, 시간 초과를 잘 고려해줘야 하는 문제.!!
  이런 식으로 dfs는 싸이클을 찾는 문제가 많은듯한데 연습이 필요하겠다..