백준 - 2606

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));
		
		int T = Integer.parseInt(br.readLine());
		graph = new ArrayList[T+1];
		
		for(int i = 0; i <= T; i++) {
			graph[i] = new ArrayList<>();
		}
		int K = Integer.parseInt(br.readLine());
		for(int i = 0; i < K; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int u = Integer.parseInt(st.nextToken());
			int v = Integer.parseInt(st.nextToken());
			
			graph[u].add(v);
			graph[v].add(u);
		}
		visited = new boolean[T+1];
		System.out.println(bfs(1));
	}
	static int bfs(int start) {
		Queue<Integer> q = new ArrayDeque<>();
		q.offer(start);
		visited[start] = true;
		
		int cnt = 0;
		while(!q.isEmpty()) {
			int v = q.poll();
			
			for(int next : graph[v]) {
				if(!visited[next]) {
					visited[next] = true;
					q.offer(next);
					++cnt;
				}
			}
		}
		return cnt;
	}
}

풀이과정 및 리뷰

1. 퍼지는 문제이므로 인접노드들을 모조리 큐에 넣어서 탐색하면서 카운트하기 위해 bfs 사용

2. 무방향 그래프이므로 양방향의 인덱스에 값을 모두 추가해 연결

3. 1에서 시작하면서, 1은 카운트 하지않으므로 큐에 인접노드를 집어넣는 시점에 ++cnt 하고,

   큐가 비어 while문을 빠져나오면 cnt를 반환하도록 함