[백준] 11724 연결 요소의 개수

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

11724번: 연결 요소의 개수

 

이 문제는 아마 제한 길이의 크기가 꽤 되서 BFS를 사용해야 되는 문제인 것 같다. 결국 그래프에 대해 BFS를 실행하는 것 자체가 결국에는 연결 요소의 갯수를 증가시키는 것이다. 방문하지 않은 인덱스를 순차적으로 탐색하면서 BFS의 시작 인덱스로 잡고, 연결된 인덱스를 방문해나가면 결과값을 구할 수 있다.

---

문제 및 입출력

---

코드

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;

public class Main
{
    // 시작 인덱스를 기준으로 BFS 실행
    public static int makeConnect(int[][] graph, boolean[] visit, int start, int n)
    {
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(start);
        visit[start] = true;
        
        while(!q.isEmpty())
        {
            int index = q.poll();
            
            for(int i=0; i<n; i++)
            {
                if(i!=start && !visit[i] && graph[index][i]==1)
                {
                    visit[i] = true;
                    q.add(i);
                }
            }
        }
        
        return 1;
    }
    public static void main(String[] args)
    {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int cnt = 0;
        int[][] graph = new int[n][n];
        boolean[] visit = new boolean[n];
        
        for(int i=0; i<m; i++)
        {
            int start = sc.nextInt()-1;
            int end = sc.nextInt()-1;
            
            // 양방향 그래프 생성
            graph[start][end] = 1;
            graph[end][start] = 1;
        }
        
        // makeConnect를 실행하는 횟수 = 연결 요소의 갯수
        for(int i=0; i<n; i++)
        {
            if(!visit[i])
            {
                cnt += makeConnect(graph, visit, i,n );
            }
        }
        
        System.out.println(cnt);
        sc.close();
    }
}