[백준] 1062번: 연결 요수의 개수 (JavaScript)

2025. 2. 20. 17:47·PS


문제

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

개념

그래프 탐색

DFS, BFS

구현 코드(JavaScript)

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

const [n, m] = input[0].split(' ').map(Number);
const graph = Array(n + 1)
  .fill(0)
  .map(() => Array(n + 1).fill(0));

for (let i = 1; i <= m; i++) {
  const [u, v] = input[i].split(' ').map(Number);
  graph[u].push(v);
  graph[v].push(u);
}

let count = 0;
const visited = Array(n + 1).fill(false);

const bfs = (start) => {
  const queue = [start];
  visited[start] = true;

  while (queue.length) {
    const node = queue.shift();
    for (let i = 0; i < graph[node].length; i++) {
      const nextNode = graph[node][i];
      if (!visited[nextNode]) {
        visited[nextNode] = true;
        queue.push(nextNode);
      }
    }
  }
};

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

console.log(count);

코드 설명

주어진 무방향 그래프에서 연결 요소의 개수를 구하는 문제입니다.

그래프는 가중치가 없는 형태이며, 이는 BFS를 사용하기에 적절한 구조입니다.

BFS를 선택한 이유?

  • 무방향 그래프에서 연결 요소의 개수를 찾는 문제는 DFS와 BFS를 사용하여 해결할 수 있습니다.
  • BFS는 큐(Queue) 를 사용하여 탐색하기 때문에, DFS에 비해 재귀 호출의 깊이가 깊어지는 문제를 방지할 수 있습니다.
  • 일반적으로 인접 행렬을 사용하면 BFS의 시간 복잡도는 O(N^2) 입니다.

입력 및 그래프 표현

입력값을 받아 2차원 인접 행렬을 생성합니다. 이를 통해 연결된 노드를 쉽게 탐색할 수 있도록 합니다.

일반적으로 탐색해야 하는 그래프의 노드가 n개라면, 인접 행렬은 n * n 의 크기로 만듭니다.

 

입력 예시

6 5
1 2
2 5
5 1
3 4
4 6

인접 행렬 표현

위 입력 예제를 기준으로 만든 인접 행렬은 다음과 같습니다.

  1 2 3 4 5 6
1 0 1 0 0 1 0
2 1 0 0 0 0 0
3 0 0 0 1 0 0
4 0 0 1 0 0 1
5 1 0 0 0 0 0
6 0 0 0 1 0 0

 

위 행렬 정보에 따르면 다음과 같이 연결되었다고 할 수 있습니다!

1 - 2 - 5    (첫 번째 연결 요소)
3 - 4 - 6    (두 번째 연결 요소)

 

 

 

  1. i = 1일 때, visited[1]이 false이므로 bfs(1) 실행 → 1, 2, 5 방문 -> count++ ( i = 2, 5는 이미 방문했으므로 건너뜀 )
  2. i = 3일 때, visited[3]이 false이므로 bfs(3) 실행 → 3, 4, 6 방문 → count++

=> 따라서, 최종적으로 카운팅하여 출력되는 값은 2입니다 😄

 

 

너비 우선 탐색(BFS) 과정 

  1. 그래프 초기화
    • graph 배열을 생성하여 인접 행렬을 만듭니다.
    • graph[u].push(v)와 graph[v].push(u)를 통해 무방향 간선을 저장합니다.
  2. 방문 여부를 체크할 배열 생성
    • visited 배열을 false로 초기화하여 방문 여부를 추적합니다.
  3. BFS 탐색 함수 구현
    • queue를 이용하여 BFS를 수행합니다.
    • 현재 노드를 queue에서 꺼내고 방문 처리한 후, 연결된 노드들을 큐에 추가합니다.
    • 위 과정을 큐에 남은 노드가 없을 때까지 반복합니다.
  4. 모든 노드를 순회하며 연결 요소 개수 계산
    • 방문하지 않은 노드를 발견하면 BFS를 실행하고 count를 증가시킵니다.
    • 방문하지 않은 노드를 발견했다는 건 이 노드가 아직 탐색되지 않은 새로운 연결 요소에 속해 있다는 뜻입니다.
    • 따라서 bfs(i)를 실행하여 해당 노드와 연결된 모든 노드를 방문 처리합니다.
      • count++를 실행하여 새로운 연결 요소를 발견했다는 사실을 기록합니다.

 

저작자표시 비영리 동일조건 (새창열림)

'PS' 카테고리의 다른 글

[백준] 7576번: 토마토 (JavaScript)  (0) 2025.02.22
[백준] 11053번: 가장 긴 증가하는 부분 수열 (JavaScript)  (0) 2025.02.21
[백준] 13904번: 과제 (JavaScript)  (0) 2025.02.20
[백준] 11659번: 구간 합 구하기 4 (JavaScript)  (0) 2025.02.19
[SWEA] 6808번: 규영이와 인영이의 카드게임 (Java)  (0) 2025.02.18
'PS' 카테고리의 다른 글
  • [백준] 7576번: 토마토 (JavaScript)
  • [백준] 11053번: 가장 긴 증가하는 부분 수열 (JavaScript)
  • [백준] 13904번: 과제 (JavaScript)
  • [백준] 11659번: 구간 합 구하기 4 (JavaScript)
abyss-s
abyss-s
프론트엔드 공부합니다.
  • abyss-s
    abyss-s의 블로그입니다.
    abyss-s
  • 전체
    오늘
    어제
    • 분류 전체보기 (188)
      • Web (16)
        • JavaScript (6)
        • TypeScript (1)
        • React (5)
        • Vue (0)
        • Storybook (1)
        • Next.js (1)
      • Backend & Infra (8)
        • Database (3)
        • Node.js (2)
        • SpringBoot (1)
      • PS (71)
      • CS (30)
        • OS (13)
        • Structure & Algorithm (5)
        • Network (10)
        • 정보처리기사 (2)
      • Language (18)
        • OOP (1)
        • JAVA (13)
        • C++ (4)
      • Activities (12)
        • 멋쟁이 사자처럼 (2)
        • OSSCA (3)
        • LG U+ URECA (3)
        • Project (2)
      • AI (0)
      • Git & Github (5)
      • Notion (1)
      • IT (4)
      • Statistics (11)
      • Book (4)
      • Diary (1)
      • Game (1)
  • 블로그 메뉴

    • 홈
    • 태그
    • 방명록
  • 링크

    • 깃허브
    • 백준
    • 트위터
  • 공지사항

    • abyss-s의 티스토리에 오신 것을 환영합니다.
  • 인기 글

  • 태그

    네트워크
    자바스크립트
    Java
    OS
    자바기반응용프로그래밍
    React
    github
    생활코딩
    C++
    백준
    통계학
    그리디
    코드트리
    JavaScript
    DP
    BFS
    BAEKJOON
    Python
    파이썬
    운영체제
  • 최근 댓글

  • 최근 글

  • hELLO· Designed By정상우.v4.10.0
abyss-s
[백준] 1062번: 연결 요수의 개수 (JavaScript)
상단으로

티스토리툴바