[JS,Node.js]백준 5567:결혼식

문제 요약

문제링크

• 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다.
• 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다.
• 상근이의 학번은 1이다.
• 첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다.
• 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다.
• 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다.
• (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다.
• 첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

문제 설계

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

const [n, , ...arr] = input;

const visited = Array.from({ length: +n + 1 }, () => false);

const graph = Array.from({ length: +n + 1 }, () => []);

arr.forEach((item, _) => {
  const [a, b] = item.split(' ').map(Number);
  graph[a].push(b);
  graph[b].push(a);
});

const dfs = (start) => {
  let stack = [[start, 0]];
  let count = 0;
  
  visited[start] = true;

  while (stack.length > 0) {
    const [curNum, depth] = stack.shift();

    if (depth > 2) continue;

    count++;

    for (const node of graph[curNum]) {
      if (!visited[node]) {
        visited[node] = true;
        stack.push([node, depth + 1]);
      }
    }
  }
  return count - 1;
};

console.log(dfs(1));

[방문 배열 생성 및 그래프 구성]

const [n, , ...arr] = input;

const visited = Array.from({ length: +n + 1 }, () => false);

const graph = Array.from({ length: +n + 1 }, () => []);
arr.forEach((item, _) => {
  const [a, b] = item.split(' ').map(Number);
  graph[a].push(b);
  graph[b].push(a);
});

방문 여부를 기록하는 배열(visited)을 생성하고, 그래프를 인접 그래프 형태로 만든다.

[DFS 초기화 및 탐색 과정]

const dfs = (start) => {
  let stack = [[start, 0]];
  let count = 0;
  
  visited[start] = true;

  while (stack.length > 0) {
    const [curNum, depth] = stack.shift();

    if (depth > 2) continue;

    count++;

    for (const node of graph[curNum]) {
      if (!visited[node]) {
        visited[node] = true;
        stack.push([node, depth + 1]);
      }
    }
  }
  return count - 1;
};

• 방문한 노드를 기록하기 위한 visited 배열과 탐색을 위한 stack을 준비한다.
• 시작 curNum(1)와 depth(0)를 스택에 넣고, 방문 배열에서 시작 노드를 방문 처리를 한다.
• 스택이 빌 때까지 반복하고, 스택에서 curNum와 depth를 꺼낸다.
• 깊이가 2를 초과하면 해당 curNum에서는 더 이상 탐색하지 않는다.
• 탐색 중 방문한 curNum의 개수에서 시작 curNum(1)를 제외한 값을 출력한다.

결론 및 추가

(추천) 그래프 개념 공부할 때 도움이 되었던 글이다.
https://velog.io/@sean2337/Algorithm-DFS%EC%99%80-BFS%EC%9D%98-%EC%89%AC%EC%9A%B4-%EA%B0%9C%EB%85%90-JavaScript-%EA%B5%AC%ED%98%84-%EB%B0%A9%EB%B2%95