[Java Algorithm] 트리 BOJ #4803

문제

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

4803번: 트리

 

내 문제 풀이

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

public class Main {

	static ArrayList<Integer>[] map;
	static boolean[] visited;
	static int n, m;
	static int cnt;
	
	public static boolean dfs(int start, int num) {
		for(int i: map[num]) { // 입력되는 숫자가 이어진 노드들 모두 확인
			if(i == start) continue; // 출발점(이전 노드) 만나면 무시
			if(visited[i]) return false; // 이미 방문한 곳 재방문 -> 싸이클 발생 !!
			visited[i] = true; // 방문 체크
			if(!dfs(num, i)) return false; // 재귀 호출 (여기 그냥 호출만 하면 안됨)
		}
		return true; // 트리 하나 찾음
	}
	
	public static void main(String[] args) throws Exception {
		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		StringBuilder out = new StringBuilder();
		
		int idx = 0;
		while(true) {
			idx++;
			cnt = 0;
			
			st = new StringTokenizer(in.readLine());
			n = Integer.parseInt(st.nextToken());
			m = Integer.parseInt(st.nextToken());
			if(n == 0 && m == 0) break; // 반복 종료 조건
			
			visited = new boolean[n];
			map = new ArrayList[n];
			for(int i = 0; i < n; i++) {
				map[i] = new ArrayList<>(); // ArrayList타입의 2차원 배열 만들기
			}
			
			for(int i = 0; i < m; i++) {
				st = new StringTokenizer(in.readLine());
				int a = Integer.parseInt(st.nextToken()) - 1;
				int b = Integer.parseInt(st.nextToken()) - 1;
				map[a].add(b);
				map[b].add(a);
			}
			
			for(int i = 0; i < n; i++) {
				if(!visited[i]) {
					visited[i] = true;
					if(dfs(-1, i)) cnt++; // 트리 찾으면 cnt++
				}
			}
			
			out.append("Case " + idx + ": ");
			if(cnt == 0) out.append("No trees.\n");
			else if(cnt == 1) out.append("There is one tree.\n");
			else out.append("A forest of " + cnt + " trees.\n");
		}
		
		System.out.println(out);
	}

}

👉 DFS 문제

• ArrayList 타입으로 2차원처럼(?) map 배열을 만들어 주었고, (크기를 가변적으로 이용하기 위함)
  모든 노드마다 이어진 노드들의 인덱스를 담았다.
• visited 배열을 돌면서 방문하지 않았던 곳을 만나면 dfs 메서드를 실행했고,
  dfs 메서드 실행 결과 true 리턴 시에만 cnt를 증가시켜 트리의 개수를 세어줬다.
• dfs함수는 start, num을 파라미터로 가지는데, start는 '이전'노드를 의미하고
  num은 현재 노드를 의미한다. (처음 시작 시 이전 노드 없으므로 -1을 넣어줬다.)
• map의 num 자리를 돌면서 num 노드와 이어지는 노드들을 탐색하는데,
  이어지는 노드가 이전 노드인 start와 같으면 탐색할 필요 없으므로 continue 했다.
  혹은 이어지는 노드의 visited 자리가 true라면 이미 방문한 곳을 재방문 했다는 의미이고,
  이 말은 싸이클이 발생했다는 뜻!! 이므로 false를 리턴해주었다.
  위 케이스 외의 경우에는 visited를 true로 바꿔주고 다음 탐색을 호출했다.
• 그런데 여기서 주의할점 ! 재귀호출 시 그냥 부르기만 하면 안됨 ! ✨ 
  싸이클이 발생한 노드가 어디까지 이어질지 모르기 때문에
  현재 contine나 return false를 만나지 못했더라도, 추후에 return false 만날 시
  현재 노드또한 싸이클에 포함되어 트리가 아니게 된다.
  따라서 dfs를 재귀호출 하면서 동시에 해당 호출의 결과가 false일 시 false를 리턴해주었다.
• 그리고 모든 탐색이 끝날 때까지 dfs가 종료되지 않았다면
  싸이클을 찾지 못했다는 의미이므로, true를 리턴해주었다.

 

✔️ 반례 추천

input
5 5
1 2
2 3
3 4
4 5
3 5
0 0

output
Case 1: No trees.

나도 이 반례를 통해 위의 주의 사항에 해당하는 예외를 찾아낼 수 있어따,,!!

안되시는 분들 한 번 해보세용

 

💡 피드백

• 싸이클을 찾는다는게 생각보다 너무 헷갈렸다ㅜ 비슷한 문제들 많이 풀어봐야겠다.