알고리즘(섬 둘레 구하기)

알고리즘(섬 둘레 구하기)

주어진 2차원 배열에서 1은 섬, 0은 바다, 배열이외에 영역도 바다라고 가정할 경우 섬의 둘레 중 가장 큰 길이를 구하는 문제이다.

ex)
input
[[0, 0, 1, 0, 0],
[0, 1, 1, 0, 1],
[0, 0, 1, 0, 1],
[1, 1, 1, 0, 1],]
output
16

function solution(map) {
  if (!map || map.length === 0) return 0;

  const rows = map.length;
  const cols = map[0].length;
  const dir = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  function dfs(i, j) {
    if (i < 0 || i >= rows || j < 0 || j >= cols || map[i][j] === 0) {
      return 1;
    }

    if (map[i][j] === -1) {
      return 0;
    }

    map[i][j] = -1;
    let perimeter = 0;

    for (const [dx, dy] of dir) {
      perimeter += dfs(i + dx, j + dy);
    }

    return perimeter;
  }

  let maxPerimeter = 0;

  for (let i = 0; i < rows; i++) {
    for (let j = 0; j < cols; j++) {
      if (map[i][j] === 1) {
        const islandPerimeter = dfs(i, j);
        maxPerimeter = Math.max(maxPerimeter, islandPerimeter);
      }
    }
  }

  return maxPerimeter;
}

// 예제 지도
const map = [
  [0, 0, 1, 0, 0],
  [0, 1, 1, 0, 1],
  [0, 0, 1, 0, 1],
  [1, 1, 1, 0, 1],
];
const map2 = [
  [1, 0, 1, 1],
  [0, 0, 1, 1],
  [1, 1, 0, 1],
  [1, 1, 0, 0],
];

console.log("가장 긴 섬의 둘레:", solution(map)); // 16
console.log("가장 긴 섬의 둘레:", solution(map2)); // 10

후기

어느 코딩테스트 나왔던 문제이다. 문제 풀 당시에는 섬의 갯수만 구하고 결국 풀지 못한 문제이다.
지금도 풀지못하여 chatGPT의 도움을 받았다. 과정은

1. map 배열을 입력으로 받는다.

2. map 배열이 유효한지 확인하고 유효하지 않다면 0 반환.

3. 배열의 행과 열 수를 변수에 저장.

4. 상하좌우를 탐색하는 방향 벡터 dir 정의

   • 재귀적으로 섬의 둘레를 계산하는 dfs (깊이 우선 탐색) 함수를 정의
   • 현재 위치가 배열의 범위를 벗어나거나 바다(0)일 경우, 둘레 길이 1을 반환
   • 이미 체크한 위치는 -1로 재할당
   • dir 배열을 사용하여 주변 위치를 탐색하고, 해당 위치가 바다(0)인 경우 둘레 길이에 1을 더한다

5. 가장 큰 섬의 둘레를 저장할 maxPerimeter 변수를 초기화

6. 모든 배열을 순회하면서 섬(1)을 찾고, 해당 위치에서 dfs 함수를 호출하여 섬의 둘레를 계산

7. 각 섬의 둘레를 maxPerimeter와 비교하여 최대 둘레를 재할당

8. 최종적으로 가장 큰 둘레인 maxPerimeter 값을 반환