백준 - 11724

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

public class Main {
    static List<Integer>[] graph;
    static boolean[] visited;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());

        graph = new ArrayList[N+1];
        for(int i = 1; i <= N; i++){
            graph[i] = new ArrayList<>();
        }

        for(int i = 0; i < M; i++){
            st = new StringTokenizer(br.readLine());
            int u = Integer.parseInt(st.nextToken());
            int v = Integer.parseInt(st.nextToken());

            connect(u,v);
        }
        visited = new boolean[N+1];
        int cnt = 1;
        bfs(1);
        for(int i = 1; i <= N; i++){
            if(!visited[i]) {
                bfs(i);
                cnt++;
            }
        }
        System.out.println(cnt);
    }
    static void connect(int u, int v){
        graph[u].add(v);
        graph[v].add(u);
    }
    static void bfs(int V){
        Queue<Integer> around = new ArrayDeque<>();
        visited[V] = true;
        around.offer(V);

        while(!around.isEmpty()){
            int v = around.poll();

            for(int next : graph[v]){
                if(!visited[next]) {
                    visited[next] = true;
                    around.offer(next);
                }
            }
        }

    }
}

풀이과정 및 리뷰

원래는 큐로 연결되지 않은 노드들을 확인하고 카운트하기 위해 bfs를 사용했지만 의도와는 다르게 코드를 썼다..

1. 인접리스트 생성 + 배열 순회하며 리스트 초기화해두는 초기작업 이후, 무방향 그래프이므로 양쪽 다 노드를 연결해서 넣어줌
2. boolean visited를 선언해 count는 1로 시작, bfs로 우선 정점을 1로 둬서 탐색 시작
3. 이후 visited배열을 돌며 값이 false인 경우 해당 노드를 정점으로 하는 bfs메서드를 호출하는 식으로 연결관계 확인하여 카운트

더 쉬운 코드

int count = 0;
        for (int i = 1; i <= N; i++) {
            if (!visited[i]) {
                dfs(i);
                count++;
            }
        }
public static void dfs(int node) {
        visited[node] = true;
        for (int next : graph.get(node)) {
            if (!visited[next]) {
                dfs(next);
            }
        }
    }

보완점

1. 큐를 사용할 필요가 전혀 없었음

• 우선 dfs 재귀호출 메서드 선언해 시작점은 visited = true 선언, 이후 해당 정점과 연결된 노드를 깊게 탐색하며 방문하지 않았다면 재귀호출 → visited배열을 순회하며 방문하지 않았을 경우 dfs(i - 시작점)를 호출해 해당 노드를 탐색하며 카운트 증가