[BOJ]11724_연결요소의개수(DFS)

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

11724번: 연결 요소의 개수

문제는 간단하다. dfs를 연습하기 좋다.

간선 정보가 주어지고, 선으로 연결된 뭉텅이? 개수를 구하는 거다.

 

0. 키포인트는 boolean[] visited를 만드는 것. 굳이 [][]만들 필요는 없음.

1. 일단 전체 mat을 돌면서 원소가 1이라면 dfs()호출!

2. dfs()에서 for문 돌면서 mat[start][i]가 1이라면 방문해주고 visited를 체크해준다.!

 

import java.util.Scanner;

public class Main {
	
	static int N, M;
	static int[][] mat;
	static boolean[] visited;
	static int[] dr = {-1,0,1,0};
	static int[] dc = {0,1,0,-1};
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		M = sc.nextInt();
		mat = new int[N+1][N+1];
		visited = new boolean[N+1];
		
		for(int i=0; i<M; i++) {
			int from = sc.nextInt();
			int to = sc.nextInt();
			mat[from][to] = mat[to][from] = 1;
		}
		
		int cnt = 0;
		for(int i=1; i<N+1; i++) {
			for(int j=1; j<N+1; j++) {
				if(!visited[i]) {
					cnt++;
					dfs(i);
				}
			}
		}
		System.out.println(cnt);
	}
	
	static void dfs(int start) {
		visited[start] = true;
		for(int i=1; i<=N; i++) {
			if(mat[start][i]==1 && !visited[i]) {
				dfs(i);
			}
		}
	}
}