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

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

4일차에 풀이했던 안전 영역과 비슷한 문제이다.
안전 영역 문제와 마찬가지로 처음에는 재귀 dfs 방식으로 풀이했다.

DFS 재귀 풀이

const fs = require("fs")
const input = fs.readFileSync("/dev/stdin").toString().split("\n").map(s => s.split(" ").map(Number))

const dx = [-1, 0, 1, -1, 1, -1, 0, 1]
const dy = [-1, -1, -1, 0, 0, 1, 1, 1]

const dfs = (map, i, j) => {
  if (!map[i][j]) return

  map[i][j] = 0
  for (let k = 0; k < dx.length; k++) {
    const x = i + dx[k]
    const y = j + dy[k]

    if (0 <= x && 0 <= y && x < map.length && y < map[0].length) {
      dfs(map, x, y)
    }
  }
}

for (let i = 0; i < input.length;) {
  const [w, h] = input[i]
  if (w === 0 && h === 0) break
  const map = input.slice(i + 1, i + 1 + h)

  let count = 0;
  for (let x = 0; x < h; x++) {
    for (let y = 0; y < w; y++) {
      if (!map[x][y]) continue
      dfs(map, x, y)
      count++
    }
  }  

  console.log(count)
  i += h + 1
}

DFS 스택 풀이

이번에는 dfs 스택 방식으로도 문제를 풀어봤다.

const fs = require("fs")
const input = fs.readFileSync("/dev/stdin").toString().split("\n").map(s => s.split(" ").map(Number))

const dx = [-1, 0, 1, -1, 1, -1, 0, 1]
const dy = [-1, -1, -1, 0, 0, 1, 1, 1]

const dfs = (map, i, j) => {
  const stack = [[i, j]]
  map[i][j] = 0

  while (stack.length) {
    const [x, y] = stack.pop()
    
    for (let k = 0; k < dx.length; k++) {
      const nx = x + dx[k]
      const ny = y + dy[k]
  
      if (0 <= nx && 0 <= ny && nx < map.length && ny < map[0].length && map[nx][ny]) {
        stack.push([nx, ny])
        map[nx][ny] = 0
      }
    }
  }
}

for (let i = 0; i < input.length;) {
  const [w, h] = input[i]
  if (w === 0 && h === 0) break
  const map = input.slice(i + 1, i + 1 + h)

  let count = 0;
  for (let x = 0; x < h; x++) {
    for (let y = 0; y < w; y++) {
      if (!map[x][y]) continue
      dfs(map, x, y)
      count++
    }
  }  

  console.log(count)
  i += h + 1
}

재귀 VS 스택

• 재귀 DFS는 호출 깊이에 따라 콜스택 오버플로우 위험이 있다. 특히 입력이 많아지거나 깊이가 깊어지면 문제가 발생할 수 있다.
• 스택 DFS는 명시적으로 스택을 사용하므로 콜스택 오버플로우 위험이 없다.
• 두 방식 모두 시간 복잡도는 O(V+E)로 동일하다. 하지만 재귀는 함수 호출 오버헤드가 있어 실제 성능에서 약간의 차이가 있을 수 있다.