DFS/BFS - 연결 요소의 개수

문제

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

분석/설계

그래프를 탐색하는 DFS/BFS 유형의 문제입니다.

구현 시 주의할 점은 방문을 체크하는 배열을 크기를 +1 해줘야 합니다.

그렇지 않을 경우 조건에서 N이 1부터 시작하기 때문에 마지막 수를 체크할 때  

Array 크기를 초과하여 Exception이 발생하게 됩니다.

구현 코드

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

public class Main {
	static int N; // 정점 개수
	static int M; // 간선 개수
	static boolean[] visited; // 방문한 곳
	static ArrayList<ArrayList<Integer>> map = new ArrayList<>(); // 그래프
	static int cnt; // 연결 요소의 개수 
	
	public static void dfs(int v) {
		visited[v] = true;
		
		for (int i=0; i<map.get(v).size(); i++) {
			int w = map.get(v).get(i);
			if (!visited[w]) dfs(w);
		}
	}
	
	public static void bfs(int v) {
		Queue<Integer> queue = new LinkedList<>();
		queue.offer(v);

		visited[v] = true;
		
		while(!queue.isEmpty()) {
			int x= queue.poll();
		
			for (int i=0; i<map.get(v).size(); i++) {
				int w = map.get(x).get(i);
				if(!visited[w]) {
					queue.offer(w);
					visited[w] = true;
				}	
			}
			
		}
		
	}
	
	public static void main(String[] args) {
		Scanner scanner = new Scanner(System.in);
		
		N = scanner.nextInt();
		M = scanner.nextInt();
		
		for(int i=0; i<=N; i++) {
			map.add(new ArrayList<>());
		}
		
		visited = new boolean[N+1];
		
		for (int i=0; i<M; i++) {
			int v1 = scanner.nextInt();
			int v2 = scanner.nextInt();
			map.get(v1).add(v2);
			map.get(v2).add(v1);
		}
		
		for(int i=1; i<=N; i++) {
			if(!visited[i]) {
				dfs(i);
				cnt++;
			}
		}	
		System.out.println(cnt);
		scanner.close();
	}
}

정리

간단하지만 조건을 정확하게 확인해야 실수를 줄일 수 있습니다.

참고

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