개발
[백준] 11742번 - 연결 요소의 개수
문제 탐색하기
1) 문제 분석
정점(vertex) : N
간선(edge) : M
M개 줄에 대한 양 끝점 : u, v
같은 간선은 1번만
2) 가능한 시간복잡도
(1) 입력 처리
첫 줄 : 정점 수 N, 간선 수 M 입력 → O(1)
그 다음 M줄 : 간선 정보 입력 → O(M)
O(M)
(2) 간선 정보 추출
M줄에서 u, v 값 추출하여 배열 생성 → O(M)
O(M)
(3) 방문 여부 배열, 인접 리스트 배열 선언
정점 수 N 기준으로 배열 2개 선언
방문 여부 배열 생성 → O(N)
인접 리스트 배열 생성 → O(N)
O(N)
(4) 그래프 구성 (간선 추가)
간선 수 M개만큼 인접 리스트에 추가 (무방향 → 2번 추가)
1개의 간선 처리 : O(1)
전체 간선 처리 : O(M)
O(M)
(5) 전체 탐색 (BFS/DFS)
모든 정점 최대 1번 방문 → O(N)
모든 간선 최대 1번씩 탐색 → O(M)
O(N + M)
(6) 결과 출력
단순 출력 → O(1)
(5) 전체 시간복잡도
입력 처리 : O(M)
간선 정보 추출 : O(M)
방문 여부 배열, 인접 리스트 배열 선언 : O(N)
그래프 구성 (간선 추가) : O(M)
전체 탐색 : O(N+M)
결과 출력 : O(1)-> 총합 : O(N+M)
3) 알고리즘 선택 이유
이 문제는 그래프에서 연결된 정점들을 하나의 묶음(연결 요소)으로 판단해야 하는 문제이다. 주어진 간선 정보를 통해 각 정점들이 서로 연결되어 있는지를 판별하고, 연결된 정점끼리는 같은 그룹으로 처리해야 한다.
따라서:
인접 리스트 형태로 그래프를 구성하고,
BFS 또는 DFS를 통해 각 정점에서 연결된 모든 정점을 순회하며 방문 처리하는 방식이 자연스럽고 효율적이다.
모든 정점과 간선을 한 번씩만 방문하면 되기 때문에, 시간 복잡도 O(N + M)의 BFS/DFS 알고리즘이 최적이다.
→ 즉, 이 문제는 그래프 탐색 기반의 BFS 또는 DFS 알고리즘을 사용하여 연결 요소 개수를 찾는 것이 가장 직관적이고 효율적인 선택이다.
잠깐! 그래프, BFS/DFS에 대한 간단한 설명, 그리고 관련 예시 문제는 여기를 참고하자.
코드 설계하기
1. 실행 구조
1) 입력 처리
정점 수(N)와 간선 수(M)를 입력받는다.
간선 정보를 공백 기준으로 나눈 후 숫자로 변환하여 2차원 배열로 저장한다.
이를 통해 그래프의 연결 정보를 구성할 수 있다.
2) 그래프 초기화
무방향 그래프이므로 인접 리스트 형태로 그래프를 생성한다.
모든 정점의 방문 여부를 기록하기 위한 visited 배열도 생성하여 초기화한다.
3) BFS 탐색 함수 구현
BFS는 큐(Queue)를 사용하여, 시작 정점으로부터 연결된 모든 정점을 방문 처리하는 함수이다.
큐에서 정점을 하나씩 꺼내면서 해당 정점과 연결된 모든 인접 정점을 방문하고 큐에 추가한다.
방문한 정점들은 다시 탐색하지 않도록 방문 처리한다.
4) 연결 요소 개수 찾기
1번부터 N번까지 모든 정점을 순회한다.
아직 방문하지 않은 정점을 발견하면 해당 정점부터 BFS를 실행하여 연결된 모든 정점을 방문 처리한다.
BFS가 실행될 때마다 연결 요소 하나가 완성된 것이므로, count 값을 1 증가시킨다.
모든 정점을 탐색한 후 count 값을 출력한다.
2. 고민이 되었던 부분
: 처음에는 어떤 방법으로 연결 요소를 찾을 수 있을지 감이 잘 오지 않았다. 연결된 정점들을 하나의 묶음으로 처리해야 했기 때문이다. 이를 해결하기 위해 두 가지 전략을 세웠다.
첫 번째, 그래프를 인접 리스트로 표현하는 것이 메모리 효율이 좋고 구현도 깔끔하다고 판단했다. 모든 간선을 양방향으로 추가하여 무방향 그래프를 완성하고, 방문 여부를 기록하기 위해 visited 배열을 선언하여 각 정점의 상태를 관리하도록 설계했다.
두 번째, 탐색 방법을 고민하다가 BFS를 선택했다. BFS는 시작점에서 가까운 노드부터 순서대로 탐색하기 때문에, 큐를 사용하여 순차적으로 연결된 정점들을 모두 탐색하는 구조가 직관적이고 구현이 쉬웠다. 새로운 정점을 만날 때마다 연결 요소 개수를 세는 방식으로 문제를 해결할 수 있었다.
1) BFS를 선택한 이유
큐를 사용하여 순서대로 탐색할 수 있어 구현이 직관적이었다.
넓게 퍼지듯 연결된 정점들을 전부 찾아가는 로직이 자연스러웠다.
재귀 호출 없이 반복문만으로 구현할 수 있다는 점도 선택 이유 중 하나였다.
2) DFS로 푸는 방법
BFS 대신 DFS를 사용하여도 동일한 결과를 얻을 수 있다.
재귀함수를 통해 한 노드에서 끝까지 깊이 탐색한 후, 인접 노드를 다시 탐색하면 된다.
function dfs(current) {
visited[current] = true;
graph[current].forEach(next => {
if (!visited[next]) {
dfs(next);
}
});
}정답 코드
// 사용 언어 : Javascript
// 입력 처리
const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split("\n");
// 첫 번째 줄 : N(정점 개수), M(간선 개수)
const [N, M] = input[0].split(" ").map(Number);
// 간선 정보 추출
input.shift();
const edges = [];
input.forEach(edge => edges.push(edge.split(" ").map(Number)));
// 방문 여부 기록 배열 (1번부터 사용, 0번 인덱스는 무시)
const visited = new Array(N + 1).fill(false);
// 인접 리스트 형태로 그래프 초기화
const graph = Array.from({ length: N + 1 }, () => []);
// 무방향 그래프 : 서로 연결된 정점 추가
for (let [u, v] of edges) {
graph[u].push(v);
graph[v].push(u);
}
// BFS 함수 : 시작 노드에서 연결된 모든 노드를 방문 처리
function bfs(start) {
const queue = [start];
visited[start] = true;
while (queue.length) {
const current = queue.shift();
graph[current].forEach(next => {
if (!visited[next]) {
visited[next] = true;
queue.push(next);
}
});
}
}
// 연결 요소 개수 세기
let count = 0;
// 1번부터 N번 정점까지 모두 확인
for (let node = 1; node <= N; node++) {
// 아직 방문하지 않은 노드라면 → 새로운 연결 요소 시작
if (!visited[node]) {
bfs(node); // 해당 노드와 연결된 모든 노드 방문 처리
count++; // 연결 요소 하나 발견했으므로 count 증가
}
}
// 연결 요소의 총 개수 출력
console.log(count);마무리하며
BFS, DFS에 대해서는 알지만, 단순히 stack, queue 정도로만 알고 있었던 스스로가 많이 성장할 수 있었던 문제였다. 특히나 이론상으로는 너무나도 잘 돌아가고, 그림으로 표현하는 것까지는 너무 쉬운데, 이걸 코드로 풀어내는 것이 고비였다. 그래도 해결 방법은 분명히 존재했고, 시간은 좀 걸리더라도 차차 풀어나갈 수 있었다.
이번 문제를 풀면서 문제를 정확하게 이해하고 추상화하는 힘이 얼마나 중요한지 다시 느낄 수 있었다. 코드 구현은 결국 내가 문제를 얼마나 잘 해석했는지를 보여주는 과정이기에, 단순히 ‘정답을 맞히는 코드’를 작성하는 것이 아니라, 문제의 상황을 어떻게 코드 구조로 풀어낼지 고민하는 과정이 훨씬 더 중요하다는 점을 체감했다.