반응형
문제
https://www.acmicpc.net/problem/2606
풀이
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
const [total, pairCount, ...pairs] = require("fs")
.readFileSync(filePath)
.toString()
.trim()
.split("\n");
const totalCnt = +total;
const connectedPairs = pairs.map((pair) => pair.split(" ").map(Number));
let graph = Array.from({ length: totalCnt + 1 }, () => []);
let ch = Array.from({ length: totalCnt + 1 }, () => 0);
let answer = 0;
// 인접 리스트
for (let [s, e] of connectedPairs) {
graph[s].push(e);
graph[e].push(s);
}
function DFS(v) {
for (let i = 0; i < graph[v].length; i++) {
const nv = graph[v][i]; // 방문할 노드
if (ch[nv] === 0) {
answer++;
ch[nv] = 1;
DFS(nv);
}
}
}
ch[1] = 1;
DFS(1);
console.log(answer);
연결되어 있는 컴퓨터들을 인접 리스트로 만들어 탐색한다.
백준에서 입력을 받은 후 값의 타입이나 구조에 유의해야겠다.
반응형
'Algorithm > BOJ' 카테고리의 다른 글
[알고리즘/백준/2667] 단지 번호 붙이기 (1) | 2023.05.23 |
---|---|
[알고리즘/백준/1325] 효율적인 해킹(BFS, JavaScript, 백준 Nodejs로 풀 때 유의사항) (4) | 2023.05.22 |
[알고리즘/백준/2178] 미로탐색(BFS, 최단거리) (1) | 2023.05.22 |
[알고리즘/백준/11725] 트리의 부모 찾기(DFS, BFS, 백준 console 시간 초과 해결) (0) | 2023.05.21 |
[알고리즘/백준/1260] DFS와 BFS(비교) (0) | 2023.05.21 |