[DFS] 음료수 얼려먹기 ( by using JavaScript )

문제 

N * M 크기의 얼음 틀이 있다. 구멍이 뚫려 있는 부분은 0 이고 칸막이가 존재하는 부분은 1이다. 즉, 0으로 연결된 부분이 얼음 한 덩이가 얼려져 나오는 것이다. 구멍이 뚫려 있는 부분 끼리 상, 하, 좌, 우로 붙어 있는 경우가 서로 연결된 경우가 된다. 이때 얼음 틀의 모양이 주어졌을 때 생성되는 총 아이스크림의 개수를 구하는 프로그램을 작성하시오.

 

 

예시

예시로 아래와 같은 얼음판의 경우를 보자.

00110 
00011 
11111 
00000

출력 

3

 

How to Solve ?

 

최초에 구멍이 뚫려있는 (=0) 을 만나면, DFS를 통해 0 주변(상,하,좌,우)에 모두 음료수를 붓는 방식으로 문제를 해결한다.

 

즉, 0을 만나서 DFS를 수행 할 때 주변에도 0이 있다면 한번에 처리를 하여 1개의 아이스크림으로 간주한다.

 

function DFS(x, y) {
  if (x <= -1 || x >= N || y <= -1 || y >= N) {
    return false;
  }

  if (iced[x][y] === 0) {
    iced[x][y] = 1;

    DFS(x - 1, y);
    DFS(x, y - 1);
    DFS(x + 1, y);
    DFS(x, y + 1);
    return true;
  }

  return false;
}

function solution() {
  let answer = 0;

  for (let i = 0; i < N; i++) {
    for (let j = 0; j < K; j++) {
      if (DFS(i, j) === true) {
        answer += 1;
      }
    }
  }
  return answer;
}

let [N, K] = [3, 3];

const iced = [
  [0, 0, 1],
  [0, 1, 0],
  [1, 0, 1],
];

console.log(solution());