99클럽 코테 스터디 6일차 TIL - 섬의 개수 (DFS/BFS)

Hyejin·2025년 4월 7일

99클럽 TIL 개발자취업 코딩테스트준비 항해99

99Club

목록 보기

7/21

문제: https://www.acmicpc.net/problem/4963
알고리즘 분류: 그래프 이론, 그래프 탐색, 너비 우선 탐색(BFS), 깊이 우선 탐색(DFS)

문제 파악

그래프 이론에서 주로 다루는 "연결 요소(Connected Components)"를 찾는 문제
섬의 개수는 연결된 땅(1)의 그룹 수를 세는 것과 같다
지도는 0(바다)과 1(땅)로 구성된 2차원 배열
가로, 세로, 대각선으로 연결된 1(땅)은 하나의 섬으로 간주

접근 방법 - `DFS(깊이우선탐색)`

지도의 모든 칸을 순회
0 땅(1)을 발견하면 해당 위치에서 DFS함수를 시작해 연결된 모든 땅을 방문하고 표시
한 번의 DFS함수가 완료되면 하나의 섬을 발견한 것이므로 섬 카운터 증가시킴
모든 칸을 순회할 때까지 1-3번 반복

내 코드

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

let lineIndex = 0;
const results = [];

while (lineIndex < input.length) {
    
  const [w, h] = input[lineIndex++].split(' ').map(Number);
  
  if (w === 0 && h === 0) break;
  
  const map = [];
  for (let i = 0; i < h; i++) {
    map.push(input[lineIndex++].split(' ').map(Number));
  }
  
  const visited = Array(h).fill().map(() => Array(w).fill(false));
  
  let islandCount = 0;
  
  for (let i = 0; i < h; i++) {
    for (let j = 0; j < w; j++) {
      if (map[i][j] === 1 && !visited[i][j]) {
        dfs(map, visited, i, j, h, w);
        islandCount++;
      }
    }
  }
  
  results.push(islandCount);
}

function dfs(map, visited, i, j, h, w) {

  if (i < 0 || i >= h || j < 0 || j >= w) return;
  
  if (visited[i][j] || map[i][j] === 0) return;
  
  visited[i][j] = true;
  
  const directions = [
    [-1, -1], [-1, 0], [-1, 1],
    [0, -1],           [0, 1],
    [1, -1],  [1, 0],  [1, 1]
  ];
  
  for (const [dx, dy] of directions) {
    dfs(map, visited, i + dx, j + dy, h, w);
  }
}

console.log(results.join('\n'));