[백준] CLASS3 11724 연결 요소의 개수 - JAVA [자바]

안녕하세요. 이번에는 백준 11724 연결 요소의 개수 문제를 풀어보려고 합니다.

 

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

11724번: 연결 요소의 개수

---

Problem

 방향 없는 그래프가 주어졌을 때, 연결 요소 (Connected Component)의 개수를 구하는 프로그램을 작성하시오.

사진 1. 문제

---

Solution

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

public class Main {

    static int[][] graph;
    static boolean[] visited;
    static int N, M;
    static int count;
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        
        N = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(st.nextToken());
        
        graph = new int[N + 1][N + 1];
        visited = new boolean[N + 1];
        count = 0;
        
        for(int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            
            int node = Integer.parseInt(st.nextToken());
            int edge = Integer.parseInt(st.nextToken());
            
            graph[node][edge] = graph[edge][node] = 1;
        }
        
        for(int i = 1; i <= N; i++) {
            if(!visited[i]) {
                bfs(i);        
                count++;
            }
        }
        
        System.out.println(count);
    }
    
    static void bfs(int start) {
        Queue<Integer> q = new LinkedList<>();
        q.offer(start);
        
        while(!q.isEmpty()) {
            int num = q.poll();
            visited[num] = true;
            
            for(int i = start; i <= N; i++) {
                if(!visited[i] && graph[num][i] == 1) {
                    visited[i] = true;
                    q.offer(i);
                }            
            }
        }             
    }
}

 이번 문제는 BFS를 사용하면 쉽게 풀 수 있는 문제이다. visited를 사용해서 방문이 안되어있으면 count++ 해주고 bfs를 통해서 연결되어 있는 요소들을 체크해 주면서 visited을 체크해주는 식으로 코드를 작성하면 된다.

 

1. 핵심 코드

static void bfs(int start) {
	Queue<Integer> q = new LinkedList<>();
	q.offer(start);
        
	while(!q.isEmpty()) {
		int num = q.poll();
		visited[num] = true;
            
		for(int i = start; i <= N; i++) {
			if(!visited[i] && graph[num][i] == 1) {
				visited[i] = true;
				q.offer(i);
			}            
		}
	}             
}

---

Performance

사진 2. 실행 결과