[백준 알고리즘] 백준 11724번 연결 요소의 개수 자바(Java)

@notepad_jj2

츄르사려고 코딩하는 코집사입니다.

---

1. [백준 알고리즘] 백준 11724번 연결 요소의 개수 자바(Java)

1) 문제번호 : 11724번

 

2) 문제 출처

www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

 

2. 문제

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

3. 제약사항

- 

4. 입력

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

 

5. 출력

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

 

6. 풀이

- 방문 배열을 만들어서 처음부터 돌면서 방문하지 않은 정점이 있다면 dfs 탐색 돌리고, 연결요소개수 1 증가

 

7. 소스 코드

import java.io.*;
import java.util.*;

public class Main {
	static int N; // 정점의 개수
	static int M; // 간선의 개수
	static int[][] adj; // 인접행렬

	static boolean[] visit; // 방문 체크

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt(); // 정점의 개수
		M = sc.nextInt(); // 간선의 개수

		adj = new int[N + 1][N + 1];

		//인접행렬 입력
		for (int i = 0; i < M; i++) {
			int a = sc.nextInt();
			int b = sc.nextInt();
			adj[a][b] = 1;
			adj[b][a] = 1;
		}
		
		visit = new boolean[N+1];

		int count = 0; // 연결요소 개수
		
		//방문 배열 돌면서 방문하지 않은 정점이 있으면 탐색하고 연결요소 개수 1 증가
		for(int i=1;i<N+1;i++) {
			if(!visit[i]) {
				dfs(i);
				count++;
			}
		}
		
		System.out.println(count);
	}
	
	public static void dfs(int start) {
		//방문했다.
		visit[start] = true;
		
		//방문 배열 처음부터 들면서 간선이 연결되어 있고, 방문을 하지 않았으면 dfs 탐색 ㄱㄱ
		for(int i=1;i<=N;i++) {
			if(adj[start][i]==1 && !visit[i]) {
				dfs(i);
			}
		}
	}
}

 

---