100. 이것이 코딩 테스트다 5장 : 음료수 얼려 먹기 Javascript

1. 문제에 대한 이해

• 우리가 풀어야 할 문제는 무엇인가?
   - 아이스크림의 개수를 구하라
• 주어진 자료는 무엇인가?
   - N x M 크기의 얼음틀
   - ices = 얼음틀의 형태가 배열로 주어진다.

2. 계획

dfs를 어떻게 구현할 수 있을지 생각이 나지 않아서 해당 책에 나와있는 파이썬 예제를 자바스크립트로 변경해서 따라서 풀었다.,,

3. 실행

• 풀이 계획을 실행하고, 각 단계가 올바른지 점검하라.

const solution = (N, M, ices) => {
  function dfs(x, y) {
    if (x <= -1 || x >= N || y <= -1 || y >= M) {
      return false;
    }

    if (ices[x][y] === 0) {
      ices[x][y] = 1;
      dfs(x - 1, y);
      dfs(x, y - 1);
      dfs(x + 1, y);
      dfs(x, y + 1);
      return true;
    }

    return false;
  }

  let answer = 0;
  for (let i = 0; i < N; i++) {
    for (let j = 0; j < M; j++) {
      if (dfs(i, j)) {
        answer += 1;
      }
    }
  }

  return answer
};

test('dfs', () => {
  expect(solution(15, 14, [
    [0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0],
    [1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0],
    [1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0],
    [1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0],
    [1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0],
    [1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
    [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1],
    [0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0],
    [0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0],
    [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1],
    [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
    [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1],
  ])).toEqual(8);
});

4. 반성

dfs, bfs 공부를 더 하고 관련 문제들을 더 풀어봐야겠다.