[백준] 11724 연결 요소의 개수 - javascript
📌 문제
https://www.acmicpc.net/problem/11724
📌 풀이
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
let [n, m] = input[0].split(" ").map(Number);
let graph = [];
for (let i = 1; i <= n; i++) {
graph[i] = [];
}
let visited = new Array(n + 1).fill(false);
for (let i = 0; i < m; i++) {
let [from, to] = input[i + 1].split(" ").map(Number);
graph[from].push(to);
graph[to].push(from);
}
function dfs(start) {
visited[start] = true;
for (let i = 0; i < graph[start].length; i++) {
let next = graph[start][i];
if (!visited[next]) {
dfs(next);
}
}
}
let ans = 0;
for (let i = 1; i <= n; i++) {
if (!visited[i]) {
dfs(i);
ans++;
}
}
console.log(ans);
✔ 알고리즘 : DFS
✔ 양방향 그래프이므로 간선 정보를 받아서 서로의 연결그래프에 추가해준다
✔ 방문한 정점을 알 수 있는 visited 배열을 false로 초기화시켜놓는다
✔ 전체 정점을 for문으로 돌면서 아직 방문하지 않았다면 dfs탐색을 시작하고 ans를 1증가 시켜준다.
❗ 그래프 연결 상태를 나타내는 배열을
let graph = new Array(n + 1);
for (let i = 0; i < graph.length; i++) {
graph[i] = new Array();
}
이렇게 구현하여 제출하였더니 런타임 에러 (SyntaxError)가 떴다
let graph = [];
for (let i = 1; i <= n; i++) {
graph[i] = [];
}
일단 이렇게 고쳐서 맞았습니다는 받았지만 왜 런타임에러가 뜨는지는 아직 잘 모르겠다...
✔ 난이도 : 백준 기준 실버2
Author And Source
이 문제에 관하여([백준] 11724 연결 요소의 개수 - javascript), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@ywc8851/백준-11724-연결-요소의-개수-javascript저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)