[콭] 음료수 얼려먹기 - DFS/BFS

문제

음료수를 얼음 틀 일부에만 넣고 얼렸다. 만들어지는 아이스크림의 총 개수를 구하라

로직

1. BFS - 큐
2. DFS - 스택
3. DFS - 재귀

풀이

BFS

function solution(n, m, s) {
  let answer = 0;
  let map = s.map((row) => row.split("").map((t) => t * 1));
  let dx = [1, -1, 0, 0];
  let dy = [0, 0, 1, -1];

  let visit = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (map[i][j] !== 1) continue;
      visit.push([i, j]);
      map[i][j] = -1;

      while (visit.length) {
        let [curX, curY] = visit.shift();
        for (let k = 0; k < 4; k++) {
          let [moveX, moveY] = [curX + dx[k], curY + dy[k]];
          if (moveX >= n || moveX < 0 || moveY >= m || moveY < 0) continue;
          if (map[moveX][moveY] !== 1) continue;
          visit.push([moveX, moveY]);
          map[moveX][moveY] = -1;
        }
      }
      answer++;
    }
  }
  console.log(answer);
}
solution(4, 5, ["00110", "00011", "01100", "00011"]);
solution(4, 5, ["00110", "00011", "11111", "00000"]);

DFS - 스택

function solution(n, m, s) {
  let answer = 0;
  let map = s.map((row) => row.split("").map((t) => t * 1));
  let dx = [1, -1, 0, 0];
  let dy = [0, 0, 1, -1];

  let visit = [];
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (map[i][j] !== 1) continue;
      visit.push([i, j]);
      map[i][j] = -1;

      while (visit.length) {
        let [curX, curY] = visit.pop();
        for (let k = 0; k < 4; k++) {
          let [moveX, moveY] = [curX + dx[k], curY + dy[k]];
          if (moveX >= n || moveX < 0 || moveY >= m || moveY < 0) continue;
          if (map[moveX][moveY] !== 1) continue;
          visit.push([moveX, moveY]);
          map[moveX][moveY] = -1;
        }
      }
      answer++;
    }
  }
  console.log(answer);
}
solution(4, 5, ["00110", "00011", "01100", "00011"]);

DFS - 재귀

function solution(n, m, s) {
  let answer = 0;
  let map = s.map((row) => row.split("").map((t) => t * 1));
  let dx = [1, -1, 0, 0];
  let dy = [0, 0, 1, -1];

  const DFS = (x, y) => {
    if (!map[x][y]) return; //0이면 return
    map[x][y] = 0;
    for (let i = 0; i < 4; i++) {
      let [moveX, moveY] = [x + dx[i], y + dy[i]];
      if (moveX >= n || moveX < 0 || moveY >= m || moveY < 0) continue;
      // map[moveX][moveY] = 0;//위에서 방문을 하고 방문 표시
      DFS(moveX, moveY);
    }
  };
  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      if (map[i][j] === 1) {
        DFS(i, j);
        answer++;
      }
    }
  }
  console.log(answer);
}
solution(4, 5, ["00110", "00011", "01100", "00011"]); //3
solution(4, 5, ["00110", "00011", "11111", "00000"]); //1