All'alba vincerò

At dawn, I will win!

Algorithm

[백준] 11724번: 연결 요소의 개수

나디아 Nadia 2024. 10. 8. 19:57

🛠️ 문제 

11724번: 연결 요소의 개수

 

 

💡 풀이

const fs = require('fs');
const path = require('path');

const input = fs.readFileSync(path.join(__dirname, 'input.txt')).toString().trim().split('\n')


const [n, m] = input[0].split(' ').map(Number); 
// n: 노드 수, m: 간선 수

const graph = Array.from({ length: n + 1 }, () => []); 
// 노드끼리 연결된 정보를 저장할 인접 리스트
// - 노드 번호가 1부터 시작하기 때문에 length: n + 1

// 그래프 구축
for (let i = 1; i <= m; i++) {
  const [u, v] = input[i].split(' ').map(Number); 
  // 두 번째 줄부터 간선 정보 가져오기

  graph[u].push(v); 
  // u의 배열에 v를 추가(= 노드 u와 노드 v가 연결됨)

  graph[v].push(u); 
  // 반대로 v의 배열에 u를 추가
}

// 노드가 방문했는지 여부를 기록
const visited = Array(n + 1).fill(false); 

// DFS 함수
const dfs = (node) => {
  // 현재 노드를 방문했는지 기록
  visited[node] = true;

  // 현재 노드와 연결된 노드들(neighbor)을 차례대로 탐색
  for (let neighbor of graph[node]) {

    // 방문하지 않은 neighbor가 있다면
    if (!visited[neighbor]) {
      // 그 노드에 대해 다시 dfs(neighbor)를 호출하여 계속해서 연결된 노드들을 탐색
      dfs(neighbor);
    }
  }
};

// 연결 요소의 개수를 저장하는 변수
let connectedComponents = 0;

// 모든 노드에 대해 DFS 수행
for (let i = 1; i <= n; i++) {

  // 아직 방문하지 않은 노드라면
  if (!visited[i]) { 
    connectedComponents++; 
    // 연결 요소 1 증가
    
    dfs(i); 
    //  그 노드를 시작점으로 DFS 수행
  }
}

// 연결 요소의 개수 출력
console.log(connectedComponents);

 

 

 

Algorithm-study/Algorithm/Solving/DFS & BFS/11724.js at main · kwonboryong/Algorithm-study

알고리즘(algorithm) 문제 풀이 스터디 . Contribute to kwonboryong/Algorithm-study development by creating an account on GitHub.

github.com

 

 

2주차 - 2일 | Notion

💡문제 분석 요약

thin-brisket-ae4.notion.site