[백준] 11724번 : 연결 요소의 개수 - JAVA [자바]

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

---

문제가 이해하기 어려웠다.

1. 연결 요소의 갯수란 몇 개 그룹으로 나뉘어졌는지에 대한 것이다.

즉, 1, 2, 3, 4, 5 그래프가 있을 때 1, 2, 3끼리 연결되고 4, 5끼리만 연결되어 있으면 이 그래프의 연결 갯수는 2개이다.

dfs 알고리즘을 이용해서 풀었다.

코드를 보자.

for (int i = 1; i <= N; i++) {
	if (!visited[i]) {
    	dfs(i);
        answer++;
	}
}

private static void dfs(int start) {
	visited[start] = true;
    for (int to : edgeList[start]) {
        if (!visited[to]) {
            dfs(to);
		}
	}
}

1. 1 번 노드부터 N 번째까지의 노드를 탐색한다.
2. 이때 i 번째 노드가 이미 방문한 적이 있으면 dfs 알고리즘을 건너뛴다.
   2.1 이미 방문한 적이 있다는 얘기는 전의 방문한 노드에서 연결되어 있는 노드란 얘기이다.
   2.2 이해가 안되면 3번 부터 읽어보자.
3. 방문하지 않은 노드를 방문한다.
4. dfs 알고리즘에 진입한다.
5. 이 노드를 방문처리하고 이 노드에서 갈 수 있는 (연결되어 있는) 노드들을 탐색한다.
6. 아직 방문하지 않았지만 갈 수 있는 노드를 start 인자로 dfs 알고리즘에 넘겨준다.
7. 4 번으로 다시 반복되고 이 알고리즘이 끝나면 처음에 들어왔던 i 노드와 연결된 모든 노드들이 방문처리되며 하나의 그룹을 완성했다고 볼 수 있다.
8. 그러므로 dfs 알고리즘을 탈출하고 그룹 갯수(answer) + 1 을 해준다.

---

public class bj11724 {

    public static int N;
    public static int M;
    public static int answer;
    public static ArrayList<Integer>[] edgeList;
    public static boolean[] visited;
    public static int[] dfsArr;
    public static StringBuilder sb = new StringBuilder();

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

        String line = br.readLine();
        String[] split = line.split(" ");

        N = Integer.parseInt(split[0]);
        M = Integer.parseInt(split[1]);
        dfsArr = new int[N];
        edgeList = new ArrayList[N + 1];
        visited = new boolean[N + 1];

        for (int i = 0; i < N + 1; i++) {
            edgeList[i] = new ArrayList<>();
        }
        for (int i = 0; i < M; i++) {
            String line1 = br.readLine();
            String[] split1 = line1.split(" ");
            int from = Integer.parseInt(split1[0]);
            int to = Integer.parseInt(split1[1]);
            edgeList[from].add(to);
            edgeList[to].add(from);
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                dfs(i);
                answer++;
            }
        }

        bw.write(answer + "\n");

        bw.flush();
        bw.close();
        br.close();
    }

    private static void dfs(int start) {
        visited[start] = true;
        for (int to : edgeList[start]) {
            if (!visited[to]) {
                dfs(to);
            }
        }
    }
}