문제 요약
정점 1..N으로 이루어진 무방향 그래프가 주어졌을 때, 그래프가 몇 개의 “덩어리(연결된 그룹)”로 나뉘어 있는지 세는 문제다.
- 어떤 정점 A에서 B로 경로가 존재하면 같은 연결 요소(같은 그룹)
- 서로 갈 수 없는 정점끼리는 다른 연결 요소
출력은 “연결 요소의 개수” 하나다.
핵심 아이디어
DFS/BFS를 “몇 번 시작했는가”
이 문제는 한 번의 DFS/BFS로 끝나지 않는다.
- 그래프가 여러 덩어리로 분리되어 있으면,
- 한 덩어리를 다 방문한 뒤에도 방문하지 않은 정점이 남는다.
- 그 “방문하지 않은 정점”에서 다시 DFS/BFS를 시작해야 한다.
따라서 정답은:
visited[i] == false인 정점을 발견할 때마다 탐색을 새로 시작하고, 그 시작 횟수를 센다.
이때 중요한 포인트는:
- DFS/BFS 내부에서 count를 올리는 게 아니라,
- 새로운 컴포넌트를 발견한 순간(탐색을 새로 시작하는 순간)
count++가 올라간다는 점이다.
공통 준비: 인접 리스트 구성
두 코드 모두 입력을 인접 리스트로 만든 뒤 탐색한다.
그래프 생성
for (int i = 0; i < node + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < line; i++) {
int nodeA = ...
int nodeB = ...
adjList.get(nodeA).add(nodeB);
adjList.get(nodeB).add(nodeA);
}- 정점 번호가 1부터라 0은 더미
- 무방향 그래프이므로 양쪽에 간선을 추가
(선택) 오름차순 정렬
for (List<Integer> list : adjList) {
list.sort(Comparator.naturalOrder());
}11724는 “방문 순서 출력”이 없어서 정렬이 필수는 아니지만, 네 코드처럼 정렬해두면 디버깅할 때 인접 노드가 일정한 순서로 보여서 편하다.
DFS 풀이 코드 흐름
DFS 버전의 핵심은 이 2개다.
- 바깥에서 1..N을 돌며 “새 컴포넌트 시작”을 감지
- dfs()는 “해당 컴포넌트 내부 노드 전부 방문 처리”만 담당
바깥 루프에서 count 증가
for (int i = 1; i <= node; i++) {
if (!visited[i]) {
count++;
dfs(i);
}
}여기서 count++는 새 연결 요소를 찾았다는 의미다.
dfs()는 방문 확장만 수행
static void dfs(int start) {
visited[start] = true;
for (int a : adjList.get(start)) {
if (!visited[a]){
dfs(a);
}
}
}- 방문했으면 true
- 인접 노드 중 미방문이면 재귀로 확장
- 같은 컴포넌트는 이 호출 한 번으로 전부 visited 처리된다
BFS 풀이 코드 흐름
BFS 버전도 구조는 동일하다.
- 바깥에서 1..N을 돌며 컴포넌트 시작점 찾기 + count 증가
- bfs()는 큐로 해당 컴포넌트를 전부 방문 처리
바깥 루프(DFS와 동일)
for (int i = 1; i <= node; i++) {
if (!visited[i]) {
count++;
bfs(i);
}
}bfs()는 큐를 비울 때까지 확장
static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()){
int target= queue.poll();
for (int a : adjList.get(target)){
if(!visited[a]){
visited[a] = true;
queue.add(a);
}
}
}
}포인트:
visited[a] = true를 큐에 넣는 시점에 해야 중복 삽입이 방지된다.- 큐가 빌 때까지 반복하면 해당 컴포넌트 전체가 방문 처리된다.
DFS 제출 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.StringTokenizer;
// 연결요소의 개수 - DFS
public class Main {
static int node;
static int line;
static List<List<Integer>> adjList = new ArrayList<>();
static boolean[] visited;
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
node = Integer.parseInt(st.nextToken());
line = Integer.parseInt(st.nextToken());
for (int i = 0; i < node + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < line; i++) {
StringTokenizer nodes = new StringTokenizer(br.readLine());
int nodeA = Integer.parseInt(nodes.nextToken());
int nodeB = Integer.parseInt(nodes.nextToken());
adjList.get(nodeA).add(nodeB);
adjList.get(nodeB).add(nodeA);
}
// 방문 순서는 상관 없지만, 기존 스타일 유지(정렬) [web:420]
for (List<Integer> list : adjList) {
list.sort(Comparator.naturalOrder());
}
visited = new boolean[node + 1];
for (int i = 1; i <= node; i++) {
if (!visited[i]) {
count++; // 새 연결요소 발견 [web:420]
dfs(i);
}
}
System.out.println(count);
}
static void dfs(int start) {
visited[start] = true;
for (int a : adjList.get(start)) {
if (!visited[a]) {
dfs(a);
}
}
}
}BFS 제출 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Comparator;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;
import java.util.StringTokenizer;
// 연결요소의 개수 - BFS
public class Main {
static int node;
static int line;
static List<List<Integer>> adjList = new ArrayList<>();
static boolean[] visited;
static int count = 0;
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine());
node = Integer.parseInt(st.nextToken());
line = Integer.parseInt(st.nextToken());
for (int i = 0; i < node + 1; i++) {
adjList.add(new ArrayList<>());
}
for (int i = 0; i < line; i++) {
StringTokenizer nodes = new StringTokenizer(br.readLine());
int nodeA = Integer.parseInt(nodes.nextToken());
int nodeB = Integer.parseInt(nodes.nextToken());
adjList.get(nodeA).add(nodeB);
adjList.get(nodeB).add(nodeA);
}
// 방문 순서는 상관 없지만, 기존 스타일 유지(정렬) [web:284]
for (List<Integer> list : adjList) {
list.sort(Comparator.naturalOrder());
}
visited = new boolean[node + 1];
for (int i = 1; i <= node; i++) {
if (!visited[i]) {
count++; // 새 연결요소 발견 [web:284]
bfs(i);
}
}
System.out.println(count);
}
static void bfs(int start) {
Queue<Integer> queue = new LinkedList<>();
queue.add(start);
visited[start] = true;
while (!queue.isEmpty()) {
int target = queue.poll();
for (int a : adjList.get(target)) {
if (!visited[a]) {
visited[a] = true;
queue.add(a);
}
}
}
}
}정리
- 연결 요소의 개수는 “그래프 덩어리 개수”
- 핵심은
for (i=1..N)로 돌며 미방문 정점 발견 시 count++ 후 탐색 시작 - DFS/BFS는 “그 컴포넌트 전체를 방문 처리하는 도구” 역할
Eazy하게