[백준] 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

좋은 웹페이지 즐겨찾기