11724번 - 연결 요소의 개수

1️⃣ BFS

 

✏️ 풀이 과정

자료구조 그래프 이론에서 등장하는 connected component의 개수를 세는 문제입니다.

 

해결 아이디어는 모든 방문하지 않은 노드에 대해서 BFS를 실행하면서 BFS의 실행 횟수를 세는 것입니다. BFS가 실행될 때마다 연결된 요소가 하나씩 모두 방문 처리되기 때문에 BFS의 실행 횟수가 연결 요소의 개수와 정확히 같습니다.

 

여기서는 인접 리스트를 사용해서 입력을 받고 visited 배열을 이용해서 방문표시를 해줬습니다. 노드 번호가 N과 같거나 작다는 조건이 있어서 간편하게 해결할 수 있었는데 없을 경우 모든 노드를 따로 저장해야합니다. 모든 노드에 대해 미방문 시 BFS를 실행하게 하고 마지막에 실행 횟수를 출력하면 문제가 해결됩니다.

💻 코드

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

public class Main {
	
	static class Node {
		int v;
		Node link;
		public Node(int v, Node link) {
			this.v = v;
			this.link = link;
		}
	}
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int start, end, cur, res = 0;;
		Node[] adjList = new Node[N+1];
		LinkedList<Integer> q = new LinkedList<>();
		boolean[] visited = new boolean[N+1];
		for(int i=0;i<M;i++) {
			st = new StringTokenizer(br.readLine());
			start = Integer.parseInt(st.nextToken());
			end = Integer.parseInt(st.nextToken());
			adjList[start] = new Node(end, adjList[start]);
			adjList[end] = new Node(start, adjList[end]);
		}
		for(int i=1;i<=N;i++) {
			if(!visited[i]) {
				q.offer(i);
				res++;
				while(!q.isEmpty()) {
					cur = q.poll();
					for(Node n=adjList[cur];n != null;n = n.link) {
						if(!visited[n.v]) {
							visited[n.v] = true;
							q.offer(n.v);
						}
					}
				}
			}
		}
		System.out.println(res);
		br.close();
	}
}