본문으로 건너뛰기

프로그래머스 - 무인도 여행

프로그래머스 - 무인도 여행​

https://school.programmers.co.kr/learn/courses/30/lessons/154540

접근 방법​

  • 가장 전형적인 방식의 격자 탐색, 또는 시뮬레이션 문제이다.
  • 우선 배열에 요소로 담겨있는 각 행별 지도 정보를 2차원 배열로 만들어준다.
  • 이중 반복문으로 각 칸을 탐색하는데, 최적화를 위해 그냥 모든 칸에 대해 dfs를 수행하지 않고, 음식이 발견되었을 때만 수행해준다.
  • 탐색은 dfs, bfs 상관없으나 구현의 편의를 위해 dfs를 선택하였다.
  • dfs 함수 내에서는 음식을 찾으면 해당 음식값을 원래 음식값에 더한뒤, 증가한 음식값을 넘겨주는 방식으로 탐색해가면서 음식값을 계속 누적한다.
  • 음식값을 찾은 칸은 “X”로 값을 변경해 다시 탐색하지 못하도록 한다.
  • 주위에서 음식을 못 찾는 경우, 누적된 음식값을 반환한다.
  • 이중 반복문에서 반환된 음식값을 받으면, 해당 음식값을 배열에 저장한다.
  • 마지막에 배열을 오름차순으로 정렬해서 반환한다. 배열이 비어있으면 [-1]을 반환해준다.

Code​

function solution(maps) {
  const answer = [];
  const rowSize = maps[0].length;
  const colSize = maps.length;
  const islandMap = maps.map((row) => row.split(""));

  const dx = [1, 0, -1, 0];
  const dy = [0, 1, 0, -1];

  const findFood = (x, y, food) => {
    for (let i = 0; i < 4; i++) {
      const nx = x + dx[i];
      const ny = y + dy[i];
      if (nx >= 0 && nx < colSize && ny >= 0 && ny < rowSize) {
        if (islandMap[nx][ny] !== "X") {
          food += Number(islandMap[nx][ny]);
          islandMap[nx][ny] = "X";
          food = findFood(nx, ny, food);
        }
      }
    }
    return food;
  };

  for (let i = 0; i < colSize; i++) {
    for (let j = 0; j < rowSize; j++) {
      if (islandMap[i][j] !== "X") {
        let tmp = Number(islandMap[i][j]);
        islandMap[i][j] = "X";
        tmp += findFood(i, j, 0);
        answer.push(tmp);
      }
    }
  }

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