[BaekJoon] 백준 11724번 _ 연결 요소의 개수 for JAVA _ DFS 알고리즘

 

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

11724번: 연결 요소의 개수

 

 

 

 

문제

 

 

 

---

 

DFS 알고리즘을 이용해 풀었다.

 

 

위의 문제는 연결 요소의 개수를 묻는 문제로 연결이 되어있는 요소의 개수를 출력하면 된다..

 

 

 

 

첫 번째 예시를 그려서 살펴보면

 

예시 1

 

 

위와 같이 나온다.

 

 

 

음....그래서 2중 ArrayList에 각 요소가 연결되어 있는 값을 넣고

 

 

visited[] 라는 배열을 만들어 방문했는지 확인하고 재귀하는 방식을 사용할 것이다.

 

 

 

 

 

코드

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


public class Baek11724 {
	public static boolean visited[] = new boolean[1000];
	public static ArrayList<ArrayList<Integer>> arrayList = new ArrayList<ArrayList<Integer>>();
	
	public static void main(String[] args) throws IOException{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		
		for(int i = 0; i < N + 1; i++)
			arrayList.add(new ArrayList<Integer>());
		
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int in1 = Integer.parseInt(st.nextToken());
			int in2 = Integer.parseInt(st.nextToken());
			arrayList.get(in1).add(in2);
			arrayList.get(in2).add(in1);
		}
		
		visited = new boolean[N + 1]; // 배열 크기 초기화
		
		int count = 0;
		for(int i = 1; i < N + 1; i++) {
			if(!visited[i]) { 
				dfs(i);
				count++;	
			}
		}
		
		System.out.println(count);
	}
	
	public static void dfs(int start) {
		
		if(visited[start]) return;
		
		visited[start] = true;
			
		for(int i = 0; i < arrayList.get(start).size(); i++) {
			int y = arrayList.get(start).get(i);
			if(!visited[y]) dfs(y);

		}
		
	}

}

 

 

 

 

성능

 

 

 

 

유니온 파인드를 사용해 풀면 효율이 더 좋긴 하다.

 

근데 어려워서 다른거 다 익히고 시간 남으면 알아보겠삼