[백준_11724] 연결 요소의 개수

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

11724번: 연결 요소의 개수

[문제]

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

 

[입력 조건]

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

 

[코드]

import java.util.*;

public class BaekJoon_11724 {
	public static int[][] graph;
	public static int n,m,count=0;
	public static boolean[] visited;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc=new Scanner(System.in);
		n=sc.nextInt();
		m=sc.nextInt();
		graph=new int[n+1][n+1];
		visited=new boolean[n+1];
		
		// 간선 연결상태 저장
		for(int i=0;i<m;i++) {
			int a=sc.nextInt();
			int b=sc.nextInt();
			
			graph[a][b]=graph[b][a]=1;
		}
		
		// 방문 배열을 탐색하면서 방문하지 않은 정점이 있다면 탐색 후 연결요소 1증가
		for(int i=1;i<=n;i++) {
			if(visited[i]==false) {
				dfs(i);
				count++;
			}
		}
		System.out.println(count);
	}
	
	public static void dfs(int index) {
		visited[index]=true; // 방문처리
		
		// 간선이 연결되어 있고, 방문하지 않았다면 dfs() 호출
		for(int i=1;i<=n;i++) {
			if(graph[index][i]==1&&visited[i]==false)
				dfs(i);
		}
	}
}

 

[고찰]

 문제만 보고 처음에는 다익스트라로 접근하려 했는데 틀린 방법이었다. 다익스트라 문제가 아닌 방문 여부에 따라 해당 노드와 연결된 모든 노드를 모두 탐색해야 하는 DFS문제였다. 문제집에 있는 문제는 카테고리가 나눠져있지 않아 어떤 알고리즘으로 풀어야 하는지 스스로 판단해야 하기 때문에 좀 더 어렵게 느껴지는 것 같다. 연습이 더 필요하다고 생각한다.