백준 11724 자바

 

 

BFS 풀이입니다.

아래 BFS 메서드는 기존과 동일합니다.

문제는 연결 요소를 구하는 것인데 연결 요소는 쉽게 말하면 나누어진 각각의 그래프입니다. 

즉, 몇 묶음으로 나뉘었는지를 구해야 합니다.

문제 입력을 보면

예제 1은

1 - 2 - 5 , 3 - 4 - 6 으로 2개가 나옵니다.

 

하지만 BFS 메서드를 보면 처음 입력 1이 들어가면 2, 5는 탐색할 수 있지만 3,4,6은 탐색을 못 합니다.

그래서 BFS 메서드는 가만히 냅두고 위에서 반복문을 이용해서 cnt를 구했습니다.

1번부터 N번까지 반복이지만 어차피 BFS를 돌면서 방문하면 true로 바뀌게 되니까 총 BFS 몇 번 도는지 (몇 개의 묶음으로 나뉘는지)를 셀 수 있습니다.

 

 

import java.util.*;
import java.io.*;
public class Main {

    static boolean[] visited;
    static ArrayList<Integer>[] list;
    static int N, M;
    static int cnt = 0;

    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());

        visited = new boolean[N+1];
        list = new ArrayList[N+1];

        for (int i = 1; i <= N; i++) {
            list[i] = new ArrayList<>();
        }
       M = Integer.parseInt(st.nextToken());

        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());

            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());

            list[a].add(b);
            list[b].add(a);
        }

        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                BFS(i);
                cnt++;
            }
        }
        System.out.println(cnt);

    }
    static void BFS(int start) {
        Queue<Integer> queue = new LinkedList<>();
        queue.add(start);
        visited[start] = true;

        while (!queue.isEmpty()) {
            int q = queue.poll();

            for (int i : list[q]) {
                if (!visited[i]) {
                    visited[i] = true;
                    queue.add(i);
                }
            }
        }
    }
}