백준 - 11724번 - 연결 요소의 개수

11724번

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

public class Main {
	static StringBuilder sb = new StringBuilder();
	static int N, M;
	static boolean[][] arr;
	static boolean[] check;

	public static void main(String[] args) throws IOException {

		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());

		arr = new boolean[N+1][N+1];
		check = new boolean[N+1];

		for (int i = 0; i<M; i++) {
			StringTokenizer st2 = new StringTokenizer(bf.readLine());
			int a = Integer.parseInt(st2.nextToken());
			int b = Integer.parseInt(st2.nextToken());
			arr[a][b] = arr[b][a] = true;
		}

		int cnt = 1;
		dfs(N);
		for (int i = 1; i<check.length; i++) {
			if (!check[i]) {
				dfs(i);
				cnt++;
			}
		}
		System.out.println(cnt);

	}

	static void dfs(int N) {
		check[N] = true;

		for (int i = 1; i<check.length; i++) {
			if (arr[N][i] && !check[i]) {
				dfs(i);
			}
		}
	}
}

풀이

---

연결된 노드그룹이 몇개 있는지 묻는 문제다.

check배열과 dfs를 구하는 메서드를 사용했다. dfs로 한번 돌렸을때 check에 false가 있다면 계속해서 dfs를 돌리게되고 이때 카운트를 세준다.

이 문제를 맞췄지만 허술한 점이 많다고 생각한다.
처음에 N가지 수가 주어지고 DFS를 사용해 한번 탐색된 숫자는 true로 만들어준다.
그치만 dfs를 사용할때마다 무조건 count를 증가시킨다. 즉, 문제에서 말하는 연결요소개수를 세준다.
만약 check배열에 false가 있어 dfs를 돌렸는데 탐색이 안되서 그대로 false가 유지되면 연결요소가 늘어난게 아닌데 말이다.
나중에 이 문제를 다시 확인해보면 좋을것같다.