99클럽 코테 스터디 4일차 TIL - 안전 영역 (DFS/BFS)

deun·2025년 4월 3일

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

99클럽 코테 스터디

목록 보기

4/20

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

접근 방식

높이 1부터 지역 내 최대 높이까지 각 높이에 대해, 해당 높이 이하인 지역은 침수된 지역(0), 그 이상인 지역은 안전 지역(1)으로 표시한 2차원 배열을 생성
생성된 배열을 순회하며 안전 지역(1)을 발견할 때마다 다음을 수행
- 해당 안전 지역을 시작점으로 연결된 모든 안전 지역을 탐색
- 탐색한 모든 안전 지역을 0으로 표시(이미 카운트한 지역 중복 방지)
- 하나의 연결된 안전 영역을 완전히 탐색할 때마다 안전 영역 카운트(count)를 1 증가
높이별로 계산된 안전 영역의 개수 중 최댓값을 찾아 최종 결과로 반환

구현 (DFS 방식)

const fs = require("fs")
const [n, ...arr] = fs.readFileSync("/dev/stdin").toString().split("\n")
const areaInfo = arr.map(s => s.split(" ").map(Number))
const maxHeight = Math.max(...areaInfo.flat())

const setSafeAreas = (areas, x, y) => {
  if (!areas[x][y]) return

  areas[x][y] = 0
  if (0 <= x - 1) setSafeAreas(areas, x - 1, y)
  if (0 <= y - 1) setSafeAreas(areas, x, y - 1)
  if (x + 1 < Number(n)) setSafeAreas(areas, x + 1, y)
  if (y + 1 < Number(n)) setSafeAreas(areas, x, y + 1)
}

let maxSafeArea = 1
for (let h = 1; h < maxHeight; h++) {
  const safeAreas = areaInfo.map(arr => arr.map(l => l <= h ? 0 : 1)) 
  let count = 0;
  for (let x = 0; x < Number(n); x++) {
    for (let y = 0; y < Number(n); y++) {
      if (safeAreas[x][y]) {
        setSafeAreas(safeAreas, x, y)
        count++
      }
    }
  }

  maxSafeArea = Math.max(maxSafeArea, count)
}

console.log(maxSafeArea)

BFS로 구현해 보기

DFS 재귀 방식으로 구현해도 이 문제에서는 스택 오버플로우가 발생하지 않지만, 값이 매우 큰 지도였다면 스택 오버플로우가 발생할 수 있어 BFS로 구현하는 연습을 해봤다.
visited라는 변수를 추가해 방문한 좌표를 표시했다.

const fs = require("fs")
const [n, ...arr] = fs.readFileSync("/dev/stdin").toString().split("\n")
const areaInfo = arr.map(s => s.split(" ").map(Number))
const maxHeight = Math.max(...areaInfo.flat())

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

const setSafeAreas = (areas, visited, x, y) => {
  const queue = [[x, y]]
  visited[x][y] = true

  while (queue.length > 0) {
    const [x, y] = queue.shift()
    
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i]
      const ny = y + dy[i]
      
      if (
        nx >= 0 && nx < Number(n) &&
        ny >= 0 && ny < Number(n) &&
        areas[nx][ny] === 1 &&
        !visited[nx][ny]
      ) {
        visited[nx][ny] = true
        queue.push([nx, ny])
      }
    }
  }
}

let maxSafeArea = 1
for (let h = 1; h < maxHeight; h++) {
  const safeAreas = areaInfo.map(arr => arr.map(l => l <= h ? 0 : 1)) 
  const visited = Array.from({ length: Number(n) }, () => Array(Number(n)).fill(false))

  let count = 0;
  for (let x = 0; x < Number(n); x++) {
    for (let y = 0; y < Number(n); y++) {
      if (safeAreas[x][y] && !visited[x][y]) {
        setSafeAreas(safeAreas, visited, x, y)
        count++
      }
    }
  }

  maxSafeArea = Math.max(maxSafeArea, count)
}

console.log(maxSafeArea)