[Baekjoon (Node.js)] 11724번 연결 요소의 개수

📄 문제

문제 사진

입출력 예제

---

📝 나의 통과 풀이

let input = require("fs")
  .readFileSync("/dev/stdin") // /dev/stdin
  .toString()
  .trim()
  .split("\n");

const [N, M] = input[0].split(" ").map(Number);
const edge = input.slice(1).map((item) => item.split(" ").map(Number));

const seokhoGraph = new Map();

edge.forEach(([from, to]) => {
  if (seokhoGraph.has(from)) {
    seokhoGraph.get(from).push(to);
  } else {
    seokhoGraph.set(from, [to]);
  }
  if (seokhoGraph.has(to)) {
    seokhoGraph.get(to).push(from);
  } else {
    seokhoGraph.set(to, [from]);
  }
});

let count = 0;
let visited = [];
for (let i = 0; i < N + 1; i++) {
  visited[i] = 0;
}
function dfs(start) {
  visited[start] = 1;
  if (!seokhoGraph.has(start)) {
    return;
  }
  const nodes = [...seokhoGraph.get(start)];
  nodes.forEach((item) => {
    if (!visited[item]) {
      dfs(item);
    }
  });
}

for (let i = 1; i <= N; i++) {
  if (!visited[i]) {
    dfs(i);
    count++;
  }
}

console.log(count);

맞았습니다!

---

⌨ 접근법

1. 입력을 잘라서 [정점, 간선] 배열 [N, M] 을 만든다. (근데  M은 안썻다... 왜 이거 지금 봤지?)

2. new Map과 반복문을 사용해서 그래프를 만든다. (class를 쓰다가팀원 'BOB' 덕분에 Map의 세계도 와봤다.)

3. DFS 관련 변수 : (루프 카운트 : count, 방문 확인용 array : visited)

4. DFS를 돌리면 이어진 연결 요소 끼리 쭉 루프를 돌며 visited 에 체크된다.

5. 각 정점마다 모두 DFS에 넣어보면서 visited에 없는 순간(여러개의 연결 요소 그룹 중 새로운 그룹을 만나는 순간) count를 올려준다.

6. 출력을 찍어보면 끝

---

📚 문제 링크

https://www.acmicpc.net/problem/11724

11724번: 연결 요소의 개수

---