백준_11724 연결 요소의 개수(자바) / DFS

시간&메모리 제한

 

문제

 

입력&출력

 

문제풀이

package com.Back;

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

public class Back_11724 {
	static int N, M,ans;
	static boolean[] visited;
	static int[][] arr;

	public static void main(String[] args) throws IOException {		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		visited = new boolean[N+1];
		
		arr = new int[N+1][N+1];
		
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			arr[a][b]=1;
			arr[b][a]=1;
		}
		
		for (int i = 1; i < N+1; i++) {
			if(!visited[i]) {
				dfs(i);
				ans++;
			}
		}
		System.out.println(ans);
		
	}

	private static void dfs(int i) {
		visited[i] = true;
		for (int j = 0; j <= N; j++) {
			if(arr[i][j]==1 && !visited[j]) {
				dfs(j);
			}
		}
	}
	
	
}

※ 내 생각

이 문제를 해결하는 방법은 DFS를 이용하는 문제라고 생각했습니다.
연결이 끊어져 있는 경우 각각의 카운트를 세는 문제입니다.
각각의 요소를 for문을 돌려서 방문처리가 되지 않은 경우에는 DFS 를 통해서 연결되어 있는 부분들에 대해서 방문처리를 해줍니다.