프로그래머스 - 무인도 여행

문제

프로그래머스 — 무인도 여행

접근 방법

상하좌우로 연결된 땅을 하나의 섬으로 보고, 섬에 속한 모든 칸의 식량을 합산한다. 아직 방문하지 않은 땅을 발견할 때마다 DFS를 시작한다.

최대 100×100개의 칸이 연결될 수 있으므로 재귀 DFS는 JavaScript 실행 환경의 호출 스택 한도를 넘을 수 있다. 명시적인 배열 스택으로 DFS를 구현한다.

스택에 넣는 시점에 식량을 합산하고 해당 칸을 "X"로 바꾼다. 이렇게 방문을 즉시 표시하면 여러 이웃에서 같은 칸을 중복 등록하지 않는다. 원본 maps는 변경하지 않고, 문자열을 나눈 별도 배열을 사용한다.

스택이 비면 한 섬의 탐색이 끝난다. 섬별 합계를 오름차순으로 정렬하고, 땅이 없다면 [-1]을 반환한다.

코드

function solution(maps) {
  const rows = maps.length
  const cols = maps[0].length
  const grid = maps.map((row) => row.split(''))
  const directions = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ]
  const totals = []

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === 'X') continue

      let total = Number(grid[row][col])
      grid[row][col] = 'X'
      const stack = [[row, col]]

      while (stack.length > 0) {
        const [currentRow, currentCol] = stack.pop()
        for (const [dr, dc] of directions) {
          const nextRow = currentRow + dr
          const nextCol = currentCol + dc
          if (
            nextRow < 0 ||
            nextRow >= rows ||
            nextCol < 0 ||
            nextCol >= cols
          ) {
            continue
          }
          if (grid[nextRow][nextCol] === 'X') continue

          total += Number(grid[nextRow][nextCol])
          grid[nextRow][nextCol] = 'X'
          stack.push([nextRow, nextCol])
        }
      }
      totals.push(total)
    }
  }

  return totals.length === 0 ? [-1] : totals.sort((a, b) => a - b)
}

복잡도와 경계 조건

행 수가 r, 열 수가 c, 섬 수가 s이면 탐색은 O(rc), 결과 정렬은 O(s log s)이다. 추가 공간은 O(rc)이다.

모두 바다인 지도, 하나의 큰 섬, 대각선으로만 접한 땅을 구분해서 확인한다. 대각선은 연결 방향에 포함되지 않는다.