[BAEKJOON_11724 - JAVA] 연결 요소의 개수

문제

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

11724번: 연결 요소의 개수

 

 

과정

1. ArrayList를 활용한 정점 및 간선 관리.
2. visit 관리를 통한 연결 요소 개수 확인.

 

 

풀이

• 연결 요소란  나누어진 각각의 그래프로 고립된 부분을 생각하면 된다.(연결 요소 = 연결 성분)
• DFS, BFS 모두 사용가능.
• 2차원 배열을 사용해도 무관하지만, ArrayList를 활용해보고자 진행.
• BufferedWrite를 사용해보고자 진행.

 

 

문제

• 처음 visit을 사용하지 않으려 간선을 -1로 설정하고 진행.
  간선이 없는 정점들의 연결요소 관리가 되지 않음. -> 해결해도 코드의 가독성이 떨어짐.
  
  해결 : 해결책으로 visit을 활용.

 

 

알고리즘 지식

• DFS or BFS
• 연결 성분

 

 

연결성분 관련 게시글

2020/06/27 - [JAVA/JAVA - 알고리즘 개념] - [Algorithm] 연결 성분(Connected Component)

[Algorithm] 연결 성분(Connected Component)

 

 

JAVA코드

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

public class BJ11724_연결요소의개수 {

	static int N, M, cnt; // 정점의 개수, 간선의 개수, 연결 요소 개수
	static ArrayList<Integer> arr[]; // 그래프를 담을 배열
	static boolean visited[]; // 방문 관리

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringBuilder sb = new StringBuilder();
		StringTokenizer st = new StringTokenizer(br.readLine());

		// input
		N = Integer.parseInt(st.nextToken());
		M = Integer.parseInt(st.nextToken());
		arr = new ArrayList[N + 1]; // 1번부터 활용하기 위한 N+1크기의 ArrayList
		visited = new boolean[N + 1]; // 1번부터 활용한 visit 관리
		int po1, po2, cnt = 0;

		for (int i = 1; i <= N; i++) {
			arr[i] = new ArrayList<Integer>(); // 각 index에 ArrayList 삽입.
		}

		// (방향 없는 그래프 = 양방향 그래프) 입력받는 간선으로 정점을 서로 추가 (add 부분)
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			po1 = Integer.parseInt(st.nextToken());
			po2 = Integer.parseInt(st.nextToken());
			arr[po1].add(po2);
			arr[po2].add(po1);
		}

		// end of input

		for (int i = 1; i <= N; i++) {
			if (!visited[i]) { // 방문 관리
				dfs(i); // 연결 요소 탐색
				cnt++; // 연결 요소 추가
			}
		}

		// output
		sb.append(cnt);
		bw.write(sb + "\n");

		bw.flush();
		bw.close();
		br.close();

	}

	// 연결 요소 탐색 DFS
	private static void dfs(int v) {
		// 방문 검색
		if (visited[v]) {
			return;
		}
		
		// 방문 체크 && 재귀
		visited[v] = true;
		for (int i : arr[v]) {
			dfs(i);
		}
	}

}