[백준 11724번/JAVA] 연결 요소의 개수

문제

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

11724번: 연결 요소의 개수

무방향 그래프에서 정점과 간선이 주어지고, 연결 요소 개수를 구하는 문제이다.

풀이

• 연결요소란?

만약 6개의 노드가 있고 위와 같이 간선이 연결되어있다면, 연결 요소는 (1, 2, 5) (3, 4, 6)두 개이다.

연결 요소는 모든 정점을 연결하는 경로를 가지고 있어야 한다.

 

• 아이디어

1. 인접 행렬을 만든다.
2. DFS 탐색을 한다.
   • 임의의 노드에서부터 자식의 자식 노드를 탐색(dfs)
   • 탐색한 노드는 방문 체크
   • 더이상 탐색할 노드가 없다면 하나의 연결 요소를 끝까지 탐색한 것이므로 return 1
   • 리턴값을 CCcount 변수에 누적하여 연결 요소의 수가 몇 개인지 구함
3. 모든 노드를 방문할 때까지 2번을 반복

코드 (수정 전)

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

public class Main {
	static int N, M;
	static boolean[] check;
	static int[][] ad;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		ad = new int[N+1][N+1]; //인접행렬
		check = new boolean[N+1]; //방문체크
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			ad[u][v] = ad[v][u] = 1;			
		}
		
		//dfs
		int trueCount = 0;
		int CCcount = 0;
		
		while(true) {
			for(int i=1; i<=N; i++) {
				if(check[i]) 
					trueCount++;
			}
			
			if(trueCount==N)
				break; //모든 노드를 다 방문했다면 while문 탈출

			for(int i=1; i<=N; i++) {
				if(check[i]==true)
					continue;
				CCcount += dfs(i);				
			}
		}
		bw.write(CCcount+" ");
		bw.close();
		
		
	}
	
	static int dfs(int x) {
		check[x] = true;
		
		for(int i=1; i<=N; i++) {
			if(ad[x][i]==1 && check[i]==false) {
				dfs(i);
			}
		}
		return 1; //dfs가 끝나면 하나의 연결요소 탐색이 끝난 것이므로 1 리턴
	}
}

코드 

수정 사항

• while문을 없앰

수정 전 : check에서 true의 개수를 세어 노드 개수와 같으면 모든 노드를 탐색한 것으로 간주해 while문을 탈출했음

수정 후 : 처음 dfs 진행 후 첫 번째 연결 요소에 포함되는 노드들은 방문체크된 상태. 1~N 노드 개수만큼 for문을 돌면서 아직 방문 안 한 노드가 있으면 또 dfs를 진행하면 됨

 

• 연결 요소 개수를 누적하는 방법을 수정

수정 전 : dfs함수에서 리턴값을 받아서 누적

수정 후 : 임의의 노드에서 시작한 dfs 탐색이 끝나면 연결 요소 하나를 모두 방문했다는 의미이므로, dfs()실행이 끝나고 나서 바로 카운트를 올려주기만 하면 됨

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

public class Main {
	static int N, M;
	static boolean[] check;
	static int[][] ad;
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st;
		
		st = new StringTokenizer(br.readLine());
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		
		ad = new int[N+1][N+1];
		check = new boolean[N+1]; 
		
		for(int i=0; i<M; i++) {
			st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			ad[u][v] = ad[v][u] = 1;			
		}
		
		
		int CCcount = 0;
		//아직 방문하지 않았다면 dfs 탐색
		for(int i=1; i<=N; i++) {
			if(check[i]==true)
				continue;
			dfs(i); 
			CCcount++; //dfs가 끝나면 하나의 연결요소 탐색이 끝난 것
		}
		
		bw.write(CCcount+" ");
		bw.close();	
	}
	
	static void dfs(int x) {
		check[x] = true;
		
		for(int i=1; i<=N; i++) {
			if(ad[x][i]==1 && check[i]==false) {
				dfs(i);
			}
		}
	}
}

 

위-수정 후

아래-수정 전

 

Note

시간이 3초로 넉넉하게 주어졌으므로 비교적 짧게 구현할 수 있는 dfs로 풀어도 되겠다는 판단을 할 수 있음