[node.js] 11724번:연결 요소의 개수

문제 링크

문제 분석

• 인접 리스트를 만드는 과정을 어떻게 할까
• 순회할 리스트 & 순회된 리스트를 체크하는 boolean 값을 가진 배열을 어떻게 세팅해볼까

문제 설계

const [i, ...arr] = input;
const [n, m] = i.split(' ');
const visit = Array(n + 1).fill(false);
const graph = Array.from({ length: n + 1 }, () => []);
arr.forEach((edge) => {
  const [u, v] = edge.split(' ').map(Number);
  graph[u].push(v);
  graph[v].push(u);
});

const dfsWithWhile = (startNode) => {
  const stack = [startNode];
  visit[startNode] = true;
  while (stack.length > 0) {
    const node = stack.pop();
    for (const neighbor of graph[node]) {
      if (!visit[neighbor]) {
        stack.push(neighbor);
        visit[neighbor] = true;
      }
    }
  }
};

let count = 0;

for (let i = 1; i <= n; i++) {
  if (!visit[i]) {
    dfsWithWhile(i);
    count++;
  }
}

console.log(count);

첫째줄에서 정점과 간선의 개수 추출

const [n, m] = i.split(' ');

n: 정점
m: 간선의 개수

방문 여부를 기록하는 배열 초기화

const visit = Array(n + 1).fill(false);

그래프를 인접 리스트 형태로 만들기

const graph = Array.from({ length: n + 1 }, () => []);
arr.forEach(edge => {
  const [u, v] = edge.split(' ').map(Number);
  graph[u].push(v);
  graph[v].push(u); 
});

• 인덱스는 0부터 시작해 +1를 해준다.
• 무방향 그래프이므로 양쪽 모두 추가한다.

정점 탐색

const dfsWithWhile = (startNode) => {
  const stack = [startNode];
  visit[startNode] = true; // 현재 정점 방문
  while (stack.length > 0) {
    const node = stack.pop();
    for (const neighbor of graph[node]) { // 연결된 모든 정점 탐색
      if (!visit[neighbor]) { // 방문하지 않는 정점만 탐색
        stack.push(neighbor);
        visit[neighbor] = true;
      }
    }
  }
};

연결 요소 개수 구하기

let count = 0;

for (let i = 1; i <= n; i++) {
  if (!visit[i]) {
    dfsWithWhile(i);
    count++;
  }
}

• 모든 정점을 순회하며 방문하지 않은 정점이면 새로운 연결 요소를 시작한다.