[ Baekjoon ] #11724 연결 요소의 개수

[Baekjoon][https://www.acmicpc.net/problem/11724]

깊이 우선 탐색(DFS) 알고리즘

예제 입력 1 > 로 주어진 각 N개의 정점을 연결하는 간선을 아래 그림과 같이 표현할 수 있다.

[풀이]

연결된 노드를 map[정점1][정점2] = 1 로 주며, 해당 노드의 방문 여부는 visit[정점] 변수로 주어

DFS 알고리즘을 탐색하며 연결된 map[정점1][정점2] && visit[정점] = 0(방문하지 않은 정점)

조건으로 연결된 정점 탐색이 끝날때마다 결과를 +1 씩 증가해주도록 풀이했다.

(* map[정점2][정점1] 또한 연결된 값이므로 =1 처리)

 

또한, 정점이 3, 연결된 간선이 1개로 아래 그림과 같이 처리된 케이스 체크를 위해

방문하지 않은 visit[정점]=0 인 케이스를 체크해서 결과값 +1씩 처리하였다.

import java.util.Scanner;

public class Main {

	static int n;
	static int m;
	static int map[][];
	static int visit[];
	static int cnt = 0;
	
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		n = sc.nextInt();
		m = sc.nextInt();
		map = new int[n+1][n+1];
		visit = new int[n+1];
		
		for(int i=0;i<m;i++)
		{
			int u = sc.nextInt();
			int v = sc.nextInt();
			
			map[u][v] = 1;
			map[v][u] = 1;
		}
		
		for(int i=1;i<=n;i++) {
			for(int j=1;j<=n;j++) {
				if(map[i][j] == 1 && visit[j] == 0) {
					getDFS(i);
					cnt++;
				}
			}
		}
		
		for(int i=1;i<=n;i++) {
			if(visit[i] == 0) {
				cnt++;
			}
		}
		
		System.out.println(cnt);
	}
	
	public static void getDFS(int x)
	{
		visit[x] = 1;
		
		for(int i=1;i<=n;i++) {
			if(map[x][i] == 1 && visit[i] == 0) {
				getDFS(i);
			}
		}
	}
}