백준 11724번 <연결요소의 개수> JAVA

백준 알고리즘 11724번

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

11724번: 연결 요소의 개수

---

11724번

입력으로 첫 줄에 정점의 수 v와 간선의 수 e가 주어지고 그 다음 e개의 줄 부터 각 간선의 양 끝점이 주어진다.

 

출력으로는 주어진 정보를 토대로 그래프를 그렸을 때 연결 요소의 개수를 구해서 출력하면 된다.

---

문제 해결

이 문제는 BFS로 해결하면 된다.

파이썬으로 해결한 포스팅이 있는데 갑자기 자바로 BFS문제를 풀어보고 싶어서 다시 풀게 되었다

https://seunghee114-blog.tistory.com/147

백준 알고리즘 <연결 요소의 개수>

 

BFS

1) 탐색 시작 노드를 큐에 넣고 방문처리한다.

2) 큐에서 노드(p)를 꺼내 p노드의 인접 노드 중 방문하지 않은 노드를 모두 큐에 넣고 방문처리한다.

3) 2)의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

각 노드가 방문되었는지 확인하여 방문되지 않았다면 BFS를 수행한다. BFS를 몇 번 수행했는지가 연결요소의 개수이다.

 

이전 포스팅의 백준 <최단경로>문제를 자바로 풀 때처럼 BFS 알고리즘의 구현보다는 그래프를 저장하는 것이 더 복잡했던 것 같다. 해당 포스팅에서는 ArrayList안에 ArrayList가 있는 타입으로 그래프를 저장했지만 이번 포스팅에서는 ArrayList 배열을 만들어서 그래프를 저장하였다. 이번 방법이 더 깔끔한 것 같다.

---

코드

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

public class Main {
	static Queue<Integer> queue = new LinkedList<>();
	static boolean[] visit;

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		String temp = bf.readLine();
		String[] temp_arr = temp.split(" ");
		int node = Integer.parseInt(temp_arr[0]);
		int edge = Integer.parseInt(temp_arr[1]);

		ArrayList<Integer>[] graph = new ArrayList[node + 1];
		for (int i = 1; i < node + 1; i++) {
			graph[i] = new ArrayList<Integer>();
		}
		for (int i = 0; i < edge; i++) {
			temp = bf.readLine();
			temp_arr = temp.split(" ");
			int n1 = Integer.parseInt(temp_arr[0]);
			int n2 = Integer.parseInt(temp_arr[1]);
			graph[n1].add(n2);
			graph[n2].add(n1);
		}
		visit = new boolean[node + 1];
		int result = 0;
		for (int i = 1; i < node + 1; i++) {
			if (visit[i]) {
				continue;
			}
			bfs(i, graph);
			result++;
		}
		System.out.println(result);
	}

	public static void bfs(int start, ArrayList<Integer>[] graph) {
		visit[start] = true;
		queue.add(start);

		while (!queue.isEmpty()) {
			int pop = queue.poll();
			ArrayList<Integer> popAL = graph[pop];
			int size = popAL.size();
			for (int i = 0; i < size; i++) {
				int n = popAL.get(i);
				if (!visit[n]) {
					visit[n] = true;
					queue.add(n);
				}
			}
		}
	}

}

---

결과

---