[BOJ 11724] 연결 요소의 개수

문제

• BOJ 11724
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

나는 DFS로 문제를 해결했다. 그래프의 간선 유무를 담은 map배열을 만들었다. 그리고 for문을 돌면서 1번 정점부터 시작해서 dfs()함수에서 방문을 표시해주고 이 정점과 연결된 다음 정점을 찾아간다. 그리고 찾은 정점에 방문 표시를 한 후 다시 dfs()로 돌면서 그 다음으로 연결된 정점을 탐색한다. 이렇게 정점1번을 출발로 간선으로 연결된 주변 정점들을 모두 찾으면 더이상 갈 곳이 없으므로 함수가 종료된다. 그럼 dfs()문에서 탈출해서 다시 for문으로 돌아와 연결요소개수인 count를 하나 증가시키고 다시 for문을 돌아 2번 정점으로 간다. 만약 2번 정점이 이미 앞에서 방문되었다면 다음 정점을 확인한다. 이를 반복하다보면 결국 정점6번까지 모두 탐색하게 되고 원하는 연결 요소 개수를 구할 수 있다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

//DFS와 BFS
```java
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

//연결 요소의 개수
public class Boj_11724 {

	static int N, M;
	static boolean[][] map; //그래프
	static boolean[] visit; //방문 정점 체크

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		String[] s = br.readLine().split(" ");
		N = Integer.parseInt(s[0]);
		M = Integer.parseInt(s[1]);

		map = new boolean[N + 1][N + 1];
		visit = new boolean[N + 1];
		
		for (int i = 0; i < M; i++) {
			String[] input = br.readLine().split(" ");
			int u = Integer.parseInt(input[0]);
			int v = Integer.parseInt(input[1]);
			map[u][v] = true;
			map[v][u] = true; //양방향이니까
		}

		//탐색 시작
		int count = 0; //연결 요소 개수
		for(int i=1; i<=N; i++) {
			if(!visit[i]) {
				dfs(i);
				count++;
			}
		}
		System.out.println(count);
	}
	
	public static void dfs(int start) {
		visit[start] = true;
		for(int j=1; j<=N; j++) {
			if(map[start][j] && visit[j] == false) {
				dfs(j);
			}
		}
	}
}