[프로그래머스] 무인도 여행 JS

문제링크

전형적인 BFS문제

모든 원소를 순회하면서 존재하는 모든 무인도를 방문하고
하나의 무인도를 발견할 때마다 bfs를 통해
해당 무인도가 가지고 있는 식량의 수를 더해나가는 방식으로 풀었습니다

방문한 무인도의 원소는 X로 변경하여 방문처리를 해줬습니다

function solution(maps) {
  //bfs 완전 탐색

  const q = [];
  const result = [];
  const r_length = maps.length;
  const c_length = maps[0].length;

  const dr = [0, 0, -1, 1];
  const dc = [1, -1, 0, 0];

  //문자열을 배열로 변환
  for (let r = 0; r < r_length; r++) {
    maps[r] = maps[r].split('');
  }

  //maps의 모든 원소를 돌면서 bfs탐색
  for (let r = 0; r < r_length; r++) {
    for (let c = 0; c < c_length; c++) {
      //무인도를 찾으면
      if (maps[r][c] === 'X') continue;

      //bfs 탐색을 통해 현재 무인도가 가지고 있는 모든 식량의 합을 구함
      let sum = 0;
      sum += Number(maps[r][c]);
      maps[r][c] = 'X';
      q.push([r, c]);

      while (q.length) {
        const [current_r, current_c] = q.shift();
        for (let i = 0; i < 4; i++) {
          const next_r = current_r + dr[i];
          const next_c = current_c + dc[i];

          if (
            next_r >= 0 &&
            next_r < r_length &&
            next_c >= 0 &&
            next_c < c_length &&
            maps[next_r][next_c] !== 'X'
          ) {
            const val = Number(maps[next_r][next_c]);
            maps[next_r][next_c] = 'X';
            sum += val;
            q.push([next_r, next_c]);
          }
        }
      }

      //하나의 무인도에 있는 식량 수 result에 푸쉬
      result.push(sum);
    }
  }

  return result.length ? result.sort((a, b) => a - b) : [-1];
}