/ BOJ

BOJ_11724_연결요소의개수_JAVA

문제 : 연결요소의개수

링크 : BOJ_11724_연결요소의개수

접근 방식

연결요소의 의미를 몰라서 검색해보았다. 연결요소란 다음과 같은 경우를 말하는 것이다.

11724_1

위와 같은 경우에 연결요소는 2개이다. 서로 연결되지 않은 노드의 집합의 개수를 연결요소라고 부른다.

나는 모든 노드에 대해 DFS 탐색을 진행하며, 모든 정점에 대해 통합되어있는 방문처리 배열을 만들어 방문상태를 찾아보고 DFS가 한 번 진행될 때마다 방문처리한 노드가 있는지 체크(각각의 연결요소 탐색)하고, 있는 경우에 카운트를 증가시키는 방법으로 풀었다.

소스 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;
import java.util.StringTokenizer;

class Node {

	int ver;
	Node link;

	public Node(int ver, Node link) {
		this.ver = ver;
		this.link = link;

	}

	@Override
	public String toString() {
		return "Node [ver=" + ver + ", link=" + link + "]";
	}
}

public class BOJ_11724_연결요소의개수 {

	static int N, M, cnt;
	static Node[] arr;
	static boolean[] totalvisit;

	public static void main(String[] args) throws NumberFormatException, IOException {

		BufferedReader in = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(in.readLine(), " ");
		N = Integer.parseInt(st.nextToken());

		M = Integer.parseInt(st.nextToken());
		totalvisit = new boolean[N + 1];
		arr = new Node[N + 1];
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(in.readLine(), " ");
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());

			arr[from] = new Node(to, arr[from]);
			arr[to] = new Node(from, arr[to]);

		}

		for (int i = 1; i <= N; i++) {
			if (arr[i] == null) {
				cnt++;
			}
			if (dfs(i, totalvisit) != 0) {
				cnt++;
			}
		}
		System.out.println(cnt);
	}

	public static int dfs(int vertex, boolean[] visited) {
		visited[vertex] = true;
		int count = 0;
		for (Node node = arr[vertex]; node != null; node = node.link) {
			if (!visited[node.ver]) {
				dfs(node.ver, visited);
				count++;
			}
		}

		return count;

	}

}

풀이 방법

  1. line 10 ~ 25 : 연결리스트로 그래프 구현하기 위한 클래스

  2. line 29 ~ 31 : dfs에 사용할 전역변수 선언

  3. line 25 ~ 51 : 값을 읽어들여 간선정보를 연결리스트로 구현하는 부분, 무향그래프이기 때문에 from-to, to-from을 동시에 저장해야한다.

  4. line 53 ~ 60 : 각 노드별로 dfs를 수행한다. dfs의 리턴값으로 0이 아닌 수가 반환되면 cnt를 1 증가시킨다. 단일 노드인 경우에는 dfs의 결과로 0이 리턴되어 연결요소임에도 처리가 되지 않아 따로 꺼내어 처리해주었다.

  5. line 61 : dfs를 모두 마친 후 cnt 출력

  6. line 64 ~ 74 : dfs 수행부분, 배열을 방문처리 해가며 계속 반복한다. 내부에 count라는 변수를 두고, 탐색이 일어날 때마다 count를 증가시키고 최종적으로 count를 리턴한다.