[백준 11724번 : 실버2] 연결 요소의 개수 ( DFS / Java)

이번 문제는 기본적인 DFS 문제였다.

 

 

 

문제를 살펴보자.

 

 

 

문제

방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 정점의 개수 N과 간선의 개수 M이 주어진다. (1 ≤ N ≤ 1,000, 0 ≤ M ≤ N×(N-1)/2) 둘째 줄부터 M개의 줄에 간선의 양 끝점 u와 v가 주어진다. (1 ≤ u, v ≤ N, u ≠ v) 같은 간선은 한 번만 주어진다.

출력

첫째 줄에 연결 요소의 개수를 출력한다.

 

 

 

 

 

문제 접근 방법

 

이번 문제는 연결되어 있는 리스트의 개수를 구하는것이여서 DFS를 통해 연결되어 있는것들만 접근을 했다.

 

DFS가 뭔지 모르겠다면 아래 링크를 통해서 보고오면 이해가 빠를것이다.

https://wpioneer.tistory.com/130?category=1023663 

[자료구조] DFS(Depth First Search) Java 구현

 

 

그리고 연결 리스트의 시작 부분을 +1 해줘서 리스트의 개수를 구했다.

 

 

소스를 보자면 아래와 같다.

 

 

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

public class Run {

	public static void main(String[] args) throws IOException {
		// TODO Auto-generated method stub
		Run a = new Run();

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		String[] nums = br.readLine().split(" ");
		
		int node = Integer.parseInt(nums[0]);
		int vertaxes = Integer.parseInt(nums[1]);
		
		LinkedList<Integer>[] link = new LinkedList[node+1];
		
		for(int i = 0;i<=node;i++) {
			link[i] = new LinkedList<Integer>();
		}
		
		for(int i = 0; i<vertaxes;i++) {
			String[] vertax = br.readLine().split(" ");
			
			int start = Integer.parseInt(vertax[0]);
			int end = Integer.parseInt(vertax[1]);
			
			link[start].add(end);
			link[end].add(start);
		}
		boolean[] visit = new boolean[node+1];
		int count = 0;
		for(int i = 1; i<link.length;i++) {
			if(!visit[i]) { //해당 노드 방문하지 않았을때 진입
				count++;
				a.dfs(visit,i,link);
			}
		}
		System.out.println(count);
	}

	public void dfs(boolean[] visit, int node, LinkedList<Integer>[] link) {
		// TODO Auto-generated method stub
		visit[node] = true;
		for(int i = 0; i<link[node].size();i++) {
			int num = link[node].get(i);
			if(!visit[num]) {
				dfs(visit,num,link);
			}
		}
		
	}
}

 

느낀점

1. DFS에서 LinkedList의 index를 헷갈리지 말자.