[백준] 11724번: 연결 요소의 개수(dfs, bfs)

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

11724번: 연결 요소의 개수

dfs 코드

import java.util.Scanner;

public class Main {
	static int N;	// 정점
	static int M;	// 간선
	static int count;		// 연결 요소의 개수
	static int graph[][];	// 무방향 그래프 
	static boolean visit[];	// 방문 여부 체크
	
	public static void dfs(int i) {
		visit[i] = true;
		for(int j=1; j<=N; j++) {
			if(graph[i][j] == 1 && visit[j] == false) {
				dfs(j);
			}
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		M = scan.nextInt();
		graph = new int[N+1][N+1]; 
		visit = new boolean[N+1];
		
		for(int i=1; i<=M; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			graph[a][b] = graph[b][a] = 1;
		}
		
		for(int i=1; i<=N; i++) {
			if(!visit[i]) {
				dfs(i);
				count ++;
			}
		}
		
		System.out.println(count);
		scan.close();
	}

}

 

 

bfs 코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main {
	static int N;	// 정점
	static int M;	// 간선
	static int count;		// 연결 요소의 개수
	static int graph[][];	// 무방향 그래프 
	static boolean visit[];	// 방문 여부 체크
	
	public static void bfs(int i) {
		Queue<Integer> q = new LinkedList<Integer>();
		q.offer(i);
		visit[i] = true;
		
		while(!q.isEmpty()) {
			int temp = q.poll();
			for(int j=1; j<=N; j++) {
				if(graph[temp][j] == 1 && visit[j] == false) {
					q.offer(j);
					visit[j] = true;
				}
			}
		}
	}

	public static void main(String[] args) {
		Scanner scan = new Scanner(System.in);
		N = scan.nextInt();
		M = scan.nextInt();
		graph = new int[N+1][N+1]; 
		visit = new boolean[N+1];

		for(int i=1; i<=M; i++) {
			int a = scan.nextInt();
			int b = scan.nextInt();
			graph[a][b] = graph[b][a] = 1;
		}
		
		for(int i=1; i<=N; i++) {
			if(!visit[i]) {
				bfs(i);
				count ++;
			}
		}
		System.out.println(count);
		scan.close();
	}

}

 

 

풀이

기존 dfs 문제와 동일하다.

연결 요소란 그래프에서 정점과 간선이 겹치지 않는 부그래프로, 모든 노드쌍에 대한 경로는 존재하는걸 가리킨다.

 

https://ratsgo.github.io/data%20structure&algorithm/2017/11/24/CC/

위와 같은 그래프의 연결요소는 4개다.

따라서 모든 정점을 탐색하면서, 방문하지 않은 정점일경우 dfs재귀함수를 돌고, 연결 요소를 ++해준다.

 

 

 

위 예제 1번의 경우 A4 좌측 그림과 같이 연결 요소가 2개가 되는데,, 직접 dfs문을 적어보면

 

 

 

dfs(1)

 -dfs(2)

  -dfs(5) 가 호출되고

더이상 연결된 간선이 없으므로 빠져나와서 다시 main 문에서 i=3부터 탐색한다.(count ++)

 

dfs(3)

 -dfs(4)

  -dfs(6) 이 호출되고

메소드는 종료된다. (count ++)