[11724번] 연결 요소의 개수 (dfs)

---

---

✅ 문제 이해

이 문제는 양방향 연결 리스트인 것을 주의하자.

[ 원본 그래프 ]

그래프 1: 1-2-5-1
그래프 2: 3-4-6

[ 인접 리스트 ]

1 -> 2, 5
2 -> 1, 5
3 -> 4
4 -> 3, 6
5 -> 1, 2

---

✅ Dfs

생각해야 할 것들
1. 원본 그래프
2. 리스트 ( 원본 그래프를 인접 리스트로 나타낸 것 )
3. 방문 배열
4. 스택 

스택의 원리 = 재귀함수의 원리
따라서, 재귀함수로 dfs를 구현할 수 있다.

다녀간 노드는 stack에 재사용하지 않는 것 주의하자.

과정을 이해하기 위해 손으로 그려보자.

---

👾 주의

boolean의 초기값은 false이다.
visited [v] == true 이면 return 시킨다.

if (visited[v]) { return; }

이 문제에서 연결 요소의 개수를 구하라는 말 = dfs가 몇 번 실행되는가
(방문홧수 아님!)
visited[i] == false 이면 dfs를 시작하기 전 count 를 1 증가시켜주고 dfs를 실행한다.
count의 결과가 출력 값이다.

if (!visited[i]) { 
	count++; 
    dfs(i);
}

---

✅ 코드

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

public class Main {
	static boolean visited[];
	static ArrayList<Integer>[] arr;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		visited = new boolean[n + 1]; //0번 사용 안함
		arr = new ArrayList[n + 1];

		//각 리스트에 대해 인접 리스트를 만들어준다.
		for (int i = 1; i < n + 1; i++) {
			arr[i] = new ArrayList<>();
		}

		//인접 리스트에 값을 대입한다.
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());

			//4 -> 5, 5 -> 4 (양방향 가능)
			arr[start].add(end);
			arr[end].add(start);
		}

		int count = 0; //dfs 갯수 즉, 답을 세는 변수

		for (int i = 1; i < n + 1; i++) {
			if (!visited[i]) { // 방문하지 않은 노드이먄
				count++;
				dfs(i);
			}
		}

		System.out.println(count);

	}

	private static void dfs(int v) {
		if (visited[v]) {
			return;
		} //현재 노드가 방문한 노드이면

		//현재 노드가 방문 노드가 아니면 방문할꺼니까 true로 설정
		visited[v] = true;
		for (int i : arr[v]) { //현재 노드에서 인접한 노드들을 다 살펴보면서
			if (!visited[i]) { //방문하지 않은 노드가 있다면
				dfs(i); //dfs를 다시 실행
			}
		}

	}


}

---