백준 - 15789

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 = 0; i < N+1; i++) {
			graph[i] = new ArrayList<>();
		}
		// 양방향 연결
		for(int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());
			graph[x].add(y);
			graph[y].add(x);
		}
		st = new StringTokenizer(br.readLine());
		
		visited = new boolean[N+1]; 
		int C = Integer.parseInt(st.nextToken());
		int start = bfs(C);
		int H = Integer.parseInt(st.nextToken());
		bfs(H);
		
		int T = Integer.parseInt(st.nextToken());

		List<Integer> list = new ArrayList<>();
		for(int j = 1; j < N+1; j++) {
			if(!visited[j]) {
				list.add(bfs(j));
			}
		}
		Collections.sort(list, Collections.reverseOrder());
		int res = 0;
		for(int i = 0; i < T; i++) {
			res += list.get(i);
		}
		System.out.println(res + start);
 	}
 	static int bfs(int target) {
 		int cnt = 1;
 		
 		visited[target] = true;
 		Queue<Integer> q = new ArrayDeque<>();
 		q.offer(target);

 		while(!q.isEmpty()) {
 			for(int next : graph[q.poll()]) {
 				if(!visited[next]) {
 					visited[next] = true;
 					q.offer(next);
 					cnt++;
 				}
 			}
 		}
 		return cnt;
 	}
}

풀이과정 및 리뷰

• 문제 접근: H왕국을 제외하고, 연결요소 수를 max순으로 정렬한 후 C왕국 연결 수 + max연결 수 * T번 반복하면 되겠다.
• 시간복잡도: $O(N + M + N log N)$
• 풀이과정
  1. 그래프 구성
     • 무방향 그래프를 인접 리스트로 구성
  2. 두 개의 BFS 수행
     • C에서 한 번 BFS → start 변수로 연결 요소 크기 저장
     • H에서도 BFS 수행 (visited로 방문 체크하므로, C와 H및 앞으로 탐색하는 연결요소들은 visited로 모두 방문체크해 재방문하지 않)
  3. 방문하지 않은 노드들로 BFS 수행
     • 각각의 연결 요소 크기를 리스트에 저장
  4. 리스트 정렬 후 T개만 선택
     • 연결 요소 중 큰 것부터 T개만 선택하여 크기 합산
  5. 정답 출력
     • start + 상위 T개의 연결 요소 크기 합
• 개선점

  1. ❗ list.get(i)에서 예외 가능성 있음

  for(int i = 0; i < T; i++) {
      res += list.get(i);
  }

  • list.size() < T인 경우 IndexOutOfBoundsException 발생 가능

  • → 안전하게 고치는 방법:

    for(int i = 0; i < Math.min(T, list.size()); i++) {
        res += list.get(i);
    }

    2. 🔧 코드 스타일 개선

  • graph = new ArrayList[N+1]; 보다는 graph = new ArrayList[N + 1];로 띄어쓰기 일관성 유지 ( 진짜 별결다 트집)

  • Collections.sort(..., Collections.reverseOrder()) → 람다로 더 간결하게 쓸 수도 있음:

bfs VS dfs?

✅ DFS vs BFS 선택 기준 (이 문제에서)

기준	DFS	BFS
연결 요소 크기 구하기	가능	가능
구현 난이도 (Java)	재귀 사용 (스택 오버플로우 위험)	큐 사용 (안전하고 직관적)
노드 방문 순서	깊이 우선	너비 우선
방문 체크와 개수 세기	재귀 안에서 cnt++ 가능	큐 안에서 cnt++ 가능
성능 차이	거의 없음	거의 없음

---

💡 이 문제에서는?

✅ BFS 추천

이유:

1. 입력 노드 수가 최대 수만 단위 → 스택 오버플로우 위험은 낮지만 무시할 수 없음
2. BFS는 재귀 없이 구현 가능 → Java에서는 안정적
3. 너비 우선이기 때문에 모든 노드에 대해 동일한 방식으로 탐색 가능 (특히 연결 요소 분리 시 좋음)
4. 코드 구조가 복잡하지 않고 직관적 (지금처럼 큐 기반으로)

---

📌 결론

BFS가 이 문제에서는 더 적절한 선택입니다.

• DFS도 기능적으로 가능하지만, Java에서는 BFS가 안정성과 가독성 면에서 유리
• 현재 코드도 BFS로 잘 짜여 있어서 유지하는 게 좋습니다.