[실버2] 11724. 연결 요소의 개수(Java)

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

11724번: 연결 요소의 개수

DFS 시작,,

---

※  문제를 요약하면 아래와 같습니다.

▶ 방향 없는 그래프에서 연결 요소의 갯수를 구하기 (== 그래프가 몇 세트 있는지 구하기)

▶  Input : 첫째 줄에 정점의 갯수 N, 간선의 갯수 M 입력, 이후 M개의 줄에서 간선의 양 끝점 u와 v제공

▶  Output : 연결 요소의 갯수 출력

---

◈ Input - 1

6 5
1 2
2 5
5 1
3 4
4 6

◈ Output - 1

2

◈ Input - 2

6 8
1 2
2 5
5 1
3 4
4 6
5 4
2 4
2 3

◈ Output - 2

1

---

 ◎  코드 작성 전, 아래와 같이 솔루션을 정리하였습니다.

▶ 그래프 탐색을 위해 방문 배열을 N+1 사이즈 만큼 선언 (0번방은 제외)

▶ 그래프 탐색을 DFS로 진행, DFS 탐색 완료 후 방문 배열이 남아있다 == 아직 그래프가 더있다

▶ 그래프를 인접리스트로 구현, DFS는 재귀로 진행

  Input-1  그래프 그림 예시 )

  Input-1  인접 리스트 예시 )

▶ DFS의 첫 재귀함수가 끝날 때마다 카운트

---

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

public class Main {
	static BufferedWriter bWriter = new BufferedWriter(new OutputStreamWriter(System.out));
	static boolean[] barrVisited;
	static ArrayList<Integer>[] arrList;

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		BufferedReader bReader = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(bReader.readLine());

		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		barrVisited = new boolean[N + 1];
		arrList = new ArrayList[N + 1]; // 인접 리스트

		for (int i = 1; i <= N; i++)
			arrList[i] = new ArrayList<Integer>();

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(bReader.readLine());
			int nParent = Integer.parseInt(st.nextToken());
			int nChild = Integer.parseInt(st.nextToken());

			// 양방향 연결
			arrList[nParent].add(nChild);
			arrList[nChild].add(nParent);
		}

		int nCount = 0;

		// 연결되있는 갯수 만큼 DFS 탐색을 하게 된다.
		// DFS의 탐색 횟수 == 연결 요소의 개수
		for (int i = 1; i <= N; i++) {
			if (!barrVisited[i]) {
				nCount++;
				DFS(i);
			}
		}

		bWriter.write(String.valueOf(nCount));
		bWriter.flush();
		bWriter.close();
	}

	public static void DFS(int nNode) throws IOException {

		if (barrVisited[nNode]) {
			return;
		}

		// 인접리스트에 해당하는 곳을 방문안했으면 탐색하자
		barrVisited[nNode] = true;
		for (int i = 0; i < arrList[nNode].size(); i++) {
			if (!barrVisited[arrList[nNode].get(i)]) {
				DFS(arrList[nNode].get(i));
			}
		}
	}
}

재밌군여~

Good Luck! (피드백 감사합니다!)