[Baekjoon] 백준 11724 연결 요소의 개수 (S2^ / DFS, 그래프) - Java

링크

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

11724번: 연결 요소의 개수

 

 

 

문제 해석

노드 N개, 간선 M개가 주어질 때 연결 요소 구하기

연결 요소 : 연결된 간선으로 연결된 노드들을 하나의 덩어리로 보았을 때, 전체 그래프의 덩어리 개수

 

 

 

코드

import java.io.*;
import java.util.*;

public class Main {
	static ArrayList<Integer>[] list;
	static boolean[] v;
	static int answer;
	
	public static void main(String[] args) throws Exception {
		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()); // 간선 수
		
		v = new boolean[N + 1];
		list = new ArrayList[N + 1];
		for (int i = 0; i < N+1; i++) {
			list[i] = new ArrayList<>();
		}

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			
			list[from].add(to);
			list[to].add(from);	
		}
		
//		print(list);
		
		answer = 0;
		for (int i = 1; i < list.length; i++) {
			if (v[i] == false) {
				v[i] = true;
				dfs(i);
				answer++;
			}
		}
		System.out.println(answer);
		
		
	}

	private static void print(ArrayList<Integer>[] list) {
		for (int i = 0; i < list.length; i++) {
			System.out.println("[" + i +"] -> " +list[i].toString());
		}
		
	}

	private static void dfs(int start) {
		if(v[start] == false) {
			return;
		}
		
		for (Integer now : list[start]) {
			if(v[now] == false) {
				v[now] = true;
				dfs(now);
			}
		}
		
	}

}

 

 

 

코드 해석

가장 기본적인 DFS 코딩임과 동시에 그래프 구현 코드입니다.

 

for문을 통해서 모든 노드를 순회할 것인데, 방문 배열 v를 사용하여 재귀를 하면서 현재 노드와 직/간접적 연결이 있는 노드는 방문처리를 진행합니다.

방문(연결)되지 않은 노드가 있는 경우에만 for문에서 다시 별도의 dfs를 통한 재귀를 수행합니다.

 

 

 

발생한 문제 & 해결 방안

~~

 

 

 

 

 

 

 

해당 코드는 에디터가 코드 연습을 위해 직접 작성하였습니다.

혹시 오류가 있거나 더 좋은 코드 방향성을 아시는 분은 댓글로 남겨주시면 감사하겠습니다!

source : https://github.com/ssh5212/conding-test-practice