[백준 11724] 연결 요소의 개수
February 11, 2023
문제
https://www.acmicpc.net/problem/11724
아이디어
- 2차원 배열을 만들어서, 각 노드의 연결 정보를 정리한다.
-
모든 노드를 대상으로 아래 로직을 수행한다.
- 이미 현재 노드를 방문했다면 다음으로 넘어간다.
- 아직 해당 노드를 방문하지 않았다면 해당 노드와 연결된 모든 노드를 방문한다.
- 연결된 모든 노드의 방문을 끝냈으면 카운트를 기록한다.
이슈
기존에 입력 데이터 파일을 불러와서 정제하는 과정에서 Array.prototype.shift()를 사용했었는데 이 때문에 시간초과가 계속 발생했었다. 사실 굳이 shift로 꺼내지 않아도 충분히 정제가 가능했었다.
소스코드
// 입력 정제
const INPUT_NAME = "i1.txt";
const filePath = process.platform === "linux" ? "/dev/stdin" : `./${__dirname.split('\\').pop()}/${INPUT_NAME}`;
const input = require("fs").readFileSync(filePath).toString().trim().split("\n").map(item => item.trim());
const [n, m] = input[0].split(" ").map(item => Number(item));
const map = Array.from({ length: n + 1 }, () => []);
for (let i = 1; i <= m; i++) {
const [u, v] = input[i].split(" ").map(item => Number(item));
map[u].push(v);
map[v].push(u);
}
// 문제
const visited = Array.from({ length: n + 1 }, () => 0);
let count = 0;
function dfs(id) {
if (visited[id]) return;
visited[id] = 1;
// 현재 탐색중인 노드와 연결된 모든 노드를 탐색
for (let i = 0; i < map[id].length; i++) {
const next = map[id][i];
if (visited[next]) continue;
dfs(map[id][i]);
}
}
function solution() {
// 전체 노드를 탐색하되, 이미 방문한 노드이면 스킵
for (let i = 1; i <= n; i++) {
if (visited[i]) continue;
dfs(i);
count++;
}
console.log(count);
}
// 실행
solution();