[백준] 11724번: 연결 요소의 개수_JAVA

문제

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

 

 

입력

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

 

즉 첫째줄은 정점의 수, 간선의 수이고

둘째 줄은 각 점이다. 아래 예시에서 1 2가 이어져 있고 2 5가 이어져 있고 5 1이 이어져 있는 그래프이다. 이런식으로 이해.

또 3 4가 이어져 있고 4 6이 이어져 있는 상태이다.

따라서 연결요소의 개수가 2가 나오도록 코딩을 해야한다.

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

 

출력

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

2

 

 

 

풀이

-연결 요소의 정의

정의만 봐서는 이해가 어려울 것이다. 아래 예시로 확인해보자.

노란색 연결요소, 초록색 연결요소가 존재한다. 

따라서 연결요소의 개수는 2이다.

 

- 위 개념만 인지하고 DFS 탐색을 하면 문제는 비교적 쉽게 풀린다.

 

- BFS 방식도 가능

 

- DFS와 BFS 방식은 간선이 연결되어 있는 정점들 사이만을 탐색할 수 있는 그래프 탐색 방법이기 때문에, 끊겨 있는 서로 다른 연결 요소들까지 탐색이 되지 않기 때문이다.

 

cf) 인접행렬 개념

---

코드

public class Problem10 {
	static int N; //정점의 개수
	static int M; //간선의 개수
	static int[][] adj; //2차원 배열인 인접 행렬
	static boolean[] visit; //방문 여부
	static int result = 0; //연결요소의 개수
	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		M = scan.nextInt();
		
		adj = new int[N + 1][N + 1];
		
		//인접행렬 입력
		for(int i = 0; i< M; i++) {
			int x = scan.nextInt();
			int y = scan.nextInt();
			adj[x][y] = 1;
			adj[y][x] = 1;
			
		}
		
		visit = new boolean[N+1];
		
		//방문 여부 배열을 돌면서 방문하지 않은 정점이 있으면 dfs 탐색을 시작하고 연결개수 1 증가시킨다.
		for(int i = 1; i < N+1; i++) {
			if(!visit[i]) {
				dfs(i);
				result++;
			}
		}
		System.out.println(result);
	}
	
	private static void dfs(int fst) {
		visit[fst] = true;
		
		//연결되어 있는 곳이 있고 방문하지 않았다면 dfs 탐색
		for(int i = 1; i <= N; i++) {
			if(adj[fst][i] == 1 && !visit[i]) {
				dfs(i);
			}
		}
		
	}

}