백준 JAVA11 11724번 : 연결 요소의 개수

Mention : DFS(깊이 우선 탐색)은 Stack 구조이다 🥞

연결 요소의 개수

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
3 초	512 MB	84498	38523	25390	42.597%

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

예제 입력 1

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

예제 출력 1

2

예제 입력 2

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

예제 출력 2

1

출처

• 문제를 만든 사람: baekjoon
• 데이터를 추가한 사람: djm03178, seoo2001, YunGoon
• 잘못된 조건을 찾은 사람: songjuh

풀이 예제

• 정점 (Node)
• 간선 (Edge)

• 연결요소의 개수 : 2개
• DFS가 총 2회 수행되어야 완전탐색
  • 연결요소의 개수가 2개
  • 연결요소의 개수가 1개라면 DFS 1회만에 완전탐색될 것

슈도 코드

N(노드 개수)
M(엣지 개수)
A(그래프 데이터 저장 인접 리스트)
visited(방문기록 저장 배열)
for(n의 개수) {
	A 인접 리스트의 각 ArrayList 초기화하기
}
for(m의 개수) {
	A 인접 리스트에 그래프 데이터 저장
}
for(n의 개수) {
	if(방문하지 않은 노드) {
	연결 요소 개수++
	DFS 실행하기
	}
}

DFS {
	if(현재노드 == 방문노드) {
		visited 배열에 현재 방문 기록하기
		현재 노드의 연결 노드 중 방문하지 않은 노드로 DFS실행하기 (재귀함수)
	}
}

Code

package dfs;

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

public class P11724_dfs {

	static ArrayList<Integer>[] A;
	static boolean visited[];

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());

		A = new ArrayList[N + 1];
		visited = new boolean[N + 1];

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

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			A[v].add(u);
			A[u].add(v);
		}
		int dfsCount = 0;
		for (int i = 1; i < N + 1; i++) {
			if (!visited[i]) {
				dfsCount++;
				DFS(i);
			}
		}
		System.out.println(dfsCount);
	}

	static void DFS(int v) {
		if (visited[v]) {
			return;
		}
		
		visited[v] = true;
		for (int i : A[v]) {
			if (visited[i] == false) {
				DFS(i);
			}
		}
	}
}