프로그래머스 JS 무인도 여행 (BFS, 이웃된 값 합산)

무인도 여행 (25) 문제 보기

---

문제 조건

// X는 바다
// 숫자는 식량
// 상하좌우 연결되면 하나의 섬

// 섬 별로 숫자의 합을 오름차순으로 반환
// 방문할 섬 없으면 -1 반환

문제 풀이

function solution(maps) {
  maps = maps.map((map) => map.split("")); // 이차원 배열로 만들기
  const row = maps.length;
  const column = maps[0].length;

  const directions = [
    [-1, 0],
    [1, 0],
    [0, -1],
    [0, 1],
  ];

  const answer = [];
  const queue = [];

  for (let i = 0; i < row; i++) {
    for (let j = 0; j < column; j++) {
      if (maps[i][j] !== "X") {
        // 식량이 있는 섬에 방문
        queue.push([i, j]);
        let foods = +maps[i][j];
        maps[i][j] = "X";

        // 이웃한 타일에서 모든 식량 수집
        while (queue.length) {
          const [x, y] = queue.shift();

          for (let [dx, dy] of directions) {
            const nx = x + dx;
            const ny = y + dy;
            const isInGrid = nx >= 0 && nx < row && ny >= 0 && ny < column;
            const canVisit = isInGrid && maps[nx][ny] !== "X";

            if (canVisit) {
              queue.push([nx, ny]);
              foods += +maps[nx][ny];
              maps[nx][ny] = "X";
            }
          }
        }
        // 하나의 섬에서 수집 가능한 식량을 기록
        answer.push(foods);
      }
    }
  }
  // 오름차순하여 반환, 또는 [-1] 반환
  return answer.length ? answer.sort((a, b) => a - b) : [-1];
}

solution(["X591X", "X1X5X", "X231X", "1XXX1"]);

1. 방문한 섬에 이웃한 타일의 합을 구하면 된다.

2. 이미 방문한 섬은 "X" 처리하여 다시 계산하지 않도록 한다.

 

식량의 합을 구하기 위해서는 bfs를 이용한다.

숫자 타일에 도달했다면, 

해당 타일을 "X"로 변경하고,

상,우,하,좌 주변 네 타일 중에서 숫자 타일을 탐색한다.

 

탐색한 타일 중 숫자타일이 있다면,

해당 타일을 "X"로 변경하고, 다시 탐색하는 과정을 더 이상 탐색할 타일이 없을 때까지 시행한다.