[JAVA] 백준 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)

같은 간선은 한 번만 주어진다.

 

출력

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

 

풀이

 

의외로 간단하다. DFS나 BFS 알고리즘을 이용해서 연결되었는지 아닌지 확인하면 됨.

 

public class bj11724 {
	private static int n, m, v; 
	private static int[][] map; 
	private static boolean[] visit;

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner s = new Scanner(System.in);
		
		n = s.nextInt(); // 정점의 개수
		m = s.nextInt(); // 간선의 개수
		
		map = new int[n+1][n+1]; 
		while(m-->0) {
			int x = s.nextInt();
			int y = s.nextInt();
			
			map[x][y]=map[y][x]=1;
		}
	
		int cnt=0; // 연결 요소의 개수
		visit = new boolean[n+1];
		for(int i=1;i<=n;i++) {
			if(!visit[i]) { // 방문한 적 없었을 때
				dfs(i);
				cnt++;
			}
		}

		System.out.println(cnt);
		
	}
	static void dfs(int s) {
		if(visit[s]) { // 이미 방문한 적 있으면
			return; // 넘어감
		}
		
		visit[s] = true; // 방문

		for(int i=1;i<=n;i++) {
			if(map[s][i] == 1) {
				dfs(i);
			}
		}
		
	}
	
}