섬나라 아일랜드(반복문을 활용)

YEONGHUN KO·2021년 11월 26일
1

ALGORITHMS - PRACTICE

목록 보기
17/50
post-thumbnail

1. 접근방법

이중포문을 만들고 next x, next y를 만드는것은 이전의 재귀함수 섬나라랑 같다. 차이점은 queue를 만드는 것이다. queue안에다가 좌표를 넣고 해당이 되면 다음 좌표를 push한다.

그리고 다시 queue에서 좌표를 뽑아서 같은 방법을 진행한다.

function islandIterative(map) {
  let dx = [-1, -1, 0, 1, 1, 1, 0, -1];
  let dy = [0, 1, 1, 1, 0, -1, -1, -1];
  let queue = [];
  let current;

  let answer = 0;

  for (let i = 0; i < map.length; i++) {
    for (let j = 0; j < map.length; j++) {
      if (map[i][j] === 1) {
        answer++;
        queue.push([i, j]);
        map[i][j] = 0;

        while (queue.length) {
          current = queue.shift();
          for (let k = 0; k < dx.length; k++) {
            let nx = current[0] + dx[k];
            let ny = current[1] + dy[k];

            if (
              nx >= 0 &&
              nx < map.length &&
              ny >= 0 &&
              ny < map.length &&
              map[nx][ny] === 1
            ) {
              map[nx][ny] = 0;
              queue.push([nx, ny]);
            }
          }
        }
      }
    }
  }
  return answer;
}

끝남! 그럼 재귀와 반복문 중 누가 더 빠른지 performance를 비교해보자.

console.log(performance.now()); // 119.88500000006752
island(map);
console.log(performance.now()); // 120.48000000140746
islandIterative(map);
console.log(performance.now()); // 120.79500000254484

빠르기는 반복문이 더 빠르다.(실제 queue를 쓰면 더 빠르겠다.) 근데 가독성하고 공간복잡도는 재귀가 더 낫다.

profile
'과연 이게 최선일까?' 끊임없이 생각하기

0개의 댓글