Programmers / Level 2 / 무인도 여행 / JS

문제 간단설명

지도는 1 x 1 사각형들로 이루어진 직사각형 격자 형태이다. 각 칸에는 'X' 또는 1에서 9사이의 자연수가 적혀있다. 'X'는 바다를 나타내며, 숫자는 무인도를 나타낸다. 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이루고, 모두 합한값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타낸다.

 

각 섬에서 최대 며칠씩 머무를 수 있는지를 배열에 오름차순으로 담아 반환하면 된다. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 반환하면 된다.

 

제한 사항

• 3 <= maps의 길이 <= 100
  • 3 <= maps[i]의 길이 <= 100
  • maps[i]는 'X' 또는 1과 9 사이의 자연수로 이루어진 문자열이다.
  • 지도는 직사각형 형태이다.

 

성공 코드

function solution(maps) {
  const totalRow = maps.length;
  const totalCol = maps[0].length;

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

  const SEA = 'X';

  const visited = Array.from({ length: totalRow }, () =>
    Array.from({ length: totalCol }, () => false)
  );

  /**
   * 인자로 받은 행과 열이 유효한 인덱스인지 boolean으로 반환하는 함수
   * @param {number} row 행
   * @param {number} col 열
   * @returns 유효하다면 true, 아니라면 false를 반환한다.
   */
  const isValid = (row, col) => {
    if (row < 0 || row >= totalRow) {
      return false;
    }
    if (col < 0 || col >= totalCol) {
      return false;
    }

    return true;
  };

  /**
   * 인자로 받은 행과 열의 칸이 속해있는 섬에서 며칠 머물 수 있는지 반환하는 함수
   *
   * @param {number} row 행
   * @param {number} col 열
   * @returns 현재 섬에서 며칠 머물 수 있는지 반환한다.
   */
  const getDayOfStay = (row, col) => {
    const queue = [[row, col]];
    let dayOfStay = Number(maps[row][col]);

    visited[row][col] = true;

    while (queue.length > 0) {
      const [curRow, curCol] = queue.shift();

      for (let d = 0; d < 4; d++) {
        const nr = curRow + dr[d];
        const nc = curCol + dc[d];

        // 유효한 인덱스가 아니라면 넘어간다.
        if (isValid(nr, nc) === false) {
          continue;
        }
        // 이미 방문한 곳이라면 넘어간다.
        if (visited[nr][nc] === true) {
          continue;
        }
        // 바다라면 넘어간다.
        if (maps[nr][nc] === SEA) {
          continue;
        }

        visited[nr][nc] = true;
        queue.push([nr, nc]);
        dayOfStay += Number(maps[nr][nc]);
      }
    }

    return dayOfStay;
  };

  const result = [];
  for (let i = 0; i < totalRow; i++) {
    for (let j = 0; j < totalCol; j++) {
      if (visited[i][j] === true) {
        continue;
      }
      if (maps[i][j] === SEA) {
        continue;
      }

      const dayOfStay = getDayOfStay(i, j);
      result.push(dayOfStay);
    }
  }

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