[알고리즘/자바스크립트] 섬 개수 세기 (Island Count)

-해당 문제는 codewars사이트의 level6 문제입니다. (1~8단계 중 8단계가 가장 쉬운 레벨)-

[문제] Given a string representation of a 2d map, return the number of islands in the map. Land spaces are denoted by a zero. Water is denoted by a dot. Rows are denoted by newlines ('\n'). Two land spaces are considered connected if they are adjacent (horizontal or vertical, but not diagonal). Too easy? Try solving it without recursion..

##Example:
You may be given the string ".0...\n.00..\n....0" as input.
This correlates to a grid, like this:

.0...
.00..
....0

This would be an example of a map that contains two islands; one with 3 pieces of land, one with 1 piece of land.

##More example:
This is 5 islands:

0...0
..0..
0...0

This is 3 islands:

..000.
..000.
..000.
.0....
..000.

 

[문제 해석] 2d 지도가 하나의 string으로 주어진다. 땅은 0으로 표현되고 바다는 .로 표현된다. \n은 줄바꿈을 의미한다. 수직, 수평으로 0이 연결되면 하나의 땅으로 간주된다. 이 지도에서 섬의 개수를 찾는 것이 문제이다. (만약 문제가 너무 쉽다고 생각되면 재귀를 사용하지 않고 문제를 풀어보아라.)

 

 

 

---

 

 

 

드디어 이 문제를 해결했다!!!!!

문제 레벨은 6레벨이라는데 나한테는 너무나도 어렵게 느껴졌었던 문제.

아마 이 문제만 거의 일주일을 붙들고 끙끙댔던 것 같은데 결국 못 풀고 넘겼었다.

이 문제를 쉽게 해결하려면 재귀를 사용하면 된다는 실마리까지 받았는데도(!) 못풀었는데 어떻게 풀게 되었냐하면(!)

 

지뢰찾기를 자바스크립트로 구현하다가 이 알고리즘 문제와 매우 비슷한 문제에 직면해버렸다.

사용자가 지뢰도 없고 숫자도 없는 빈 칸을 클릭했을때, 주변 빈칸이 연쇄적으로 사라지게 해야하는데 거기서 멘붕...

 

섬찾기 문제는 그래도 2차 배열에서 위, 아래, 왼쪽, 오른쪽만 확인하면 되는데,

지뢰찾기는 심지어 대각선 방향까지 8개의 칸을 확인해야해서 더더욱 복잡했다는거...

 

이번에도 거의 며칠을 끙끙대면서 이 방법, 저 방법 다 해보다가 결국 재귀로 풀었다.

그리고 어려운 지뢰찾기 빈 칸 문제를 해결하고 나니까 섬 찾기는 정말 금방 풀었다. 

거의 몇 주를 저 문제로 괴로워하며 씨름하던 것이 허무할 정도로ㅋㅋ...

 

 

 

function countIslands (mapStr) {
  let mapArr = [];
  mapStr.split('\n').forEach(function (line) {
    mapArr.push(line.split(''));
  });
  
  let cnt = 0;
  mapArr.forEach(function (line, i) {
    line.forEach(function (item, j) {
      if (item === '0') {
        cnt++;
        destroyConnected(i, j);
      }
    });
  });

  function destroyConnected (in1, in2) {
    mapArr[in1][in2] = '.';

    if (in1 > 0) {
      if (mapArr[in1 - 1][in2] === '0') { destroyConnected(in1 - 1, in2); }
    }
    if (in2 > 0) {
      if (mapArr[in1][in2 - 1] === '0') { destroyConnected(in1, in2 - 1); }
    }
    if (in1 < mapArr.length - 1) {
      if (mapArr[in1 + 1][in2] === '0') { destroyConnected(in1 + 1, in2); }
    }
    if (in1 < mapArr[in1].length - 1) {
      if (mapArr[in1][in2 + 1] === '0') { destroyConnected(in1, in2 + 1); }
    }
  }

  return cnt;
}

 

 

먼저 string 형태로 입력받은 지도를 2차 배열의 형태로 변환한다.

 

 

 

이제 배열의 첫 번째 요소부터 iterate를 시작하여 '0'을 만나면 cnt 변수를 1 증가시킨 후,

destroyConnected() 함수에 '0'의 인덱스 번호를 인자로 넘겨주고 호출한다.

 

이 함수는 인자로 받은 인덱스 번호로 해당 위치의 요소를 '0'에서 '.'로 변경한 후

위, 아래, 왼쪽, 오른쪽을 검사하여 '0'이 있는지 검사한다.

만약에 '0'을 만나면 그 위치의 인덱스 번호를 인자로 하여 destroyConnected() 함수를 호출한다.

 

그러면 다시 그 함수는 '0'을 '.'으로 바꾸고 다시 그 주변을 검색할 것이다.

주변에 '0'인 요소가 하나도 없을 경우 함수 실행을 종료하고 다시 iterate를 시작할 것이다.

 

첫 번째 찾은 '0' 주변의 모든 '0'은 '.'로 변경되었으므로 계속 패스하다가

첫 번째 섬과 아무 접점이 없던 '0'을 만나 다시 위의 과정을 반복하게 된다.

 

결과적으로 cnt 변수에는 섬 개수가 들어있으므로 cnt 변수를 return한다.