[programmers] 무인도 여행

📝 [Lv2] 무인도 여행

👀 문제 설명

메리는 여름을 맞아 무인도로 여행을 가기 위해 지도를 보고 있습니다. 지도에는 바다와 무인도들에 대한 정보가 표시돼 있습니다. 지도는 1 x 1크기의 사각형들로 이루어진 직사각형 격자 형태이며, 격자의 각 칸에는 'X' 또는 1에서 9 사이의 자연수가 적혀있습니다. 지도의 'X'는 바다를 나타내며, 숫자는 무인도를 나타냅니다. 이때, 상, 하, 좌, 우로 연결되는 땅들은 하나의 무인도를 이룹니다. 지도의 각 칸에 적힌 숫자는 식량을 나타내는데, 상, 하, 좌, 우로 연결되는 칸에 적힌 숫자를 모두 합한 값은 해당 무인도에서 최대 며칠동안 머물 수 있는지를 나타냅니다. 어떤 섬으로 놀러 갈지 못 정한 메리는 우선 각 섬에서 최대 며칠씩 머물 수 있는지 알아본 후 놀러갈 섬을 결정하려 합니다.

지도를 나타내는 문자열 배열 maps가 매개변수로 주어질 때, 각 섬에서 최대 며칠씩 머무를 수 있는지 배열에 오름차순으로 담아 return 하는 solution 함수를 완성해주세요. 만약 지낼 수 있는 무인도가 없다면 -1을 배열에 담아 return 해주세요.

 

🚨 제한 사항

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

 

💻 입출력 예

maps	result
["X591X","X1X5X","X231X", "1XXX1"]	[1, 1, 27]
["XXX","XXX","XXX"]	[-1]

 

✨ 풀이 설명

섬 개수 세기 같은 전형적인 DFS 문제라고 생각하고 풀었다.
코드는 크게 메인 함수(solution)와 섬에서 며칠을 머물 수 있는지 계산하는 함수(island)로 나눌 수 있다.

먼저 메인 함수는 사방으로 갈 수 있는 좌표와 지도의 가로, 세로 길이 상수, 각 섬의 점수를 넣을 상수로 이루어져 있다.
그리고 인덱스의 값을 변경할 수 있도록 각 배열값이 문자열인 maps를 이차원 배열로 변형해 주었다.
메인 함수에서는 각 섬으로 진입하는 위치를 찾아 island로 좌표를 넘겨주는 역할을 한다. (이중 for문이 그 부분)

island는 내부 total이라는 변수에 해당 섬의 모든 일수를 더한다. 초기값으로는 진입한 섬의 일수를 설정해주었다.
더해진 일수가 있던 좌표는 'X'로 변경하여 다시 방문하지 않도록 해준다.
그리고 DFS 로직을 통해 재귀적으로 해당 섬의 범위를 찾고, 일수를 total에 더해준다. 해당 위치에서 사방으로 이동하며 'X'가 아닌 곳, 숫자로 쓰인 곳을 찾아다니면 된다.
더 이상 갈 곳이 없으면 DFS는 자동으로 종료되고, island 함수도 total을 반환하면 된다.

이렇게 구한 모든 섬의 값을 answer에 추가하고, 반환 시 길이를 확인하여 배열의 값이 존재한다면 오름차순 정렬하여 반환하고, 값이 없다면 [-1]을 반환해 주었다.

 

🕵️‍♂️ 코드

function solution(maps) {

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

  const ROW = maps.length, COL = maps[0].length, answer = [];

  maps = maps.map(line => line.split(''));

  const island = (i, j) => {

    let total = +maps[i][j];

    maps[i][j] = 'X';

    const DFS = (x, y) => {

      for (const [dx, dy] of DIR) {

        if (x + dx >= 0 && x + dx < ROW && y + dy >= 0 && y + dy < COL && maps[x + dx][y + dy] !== 'X') {

          total += +maps[x + dx][y + dy];

          maps[x + dx][y + dy] = 'X';

          DFS(x + dx, y + dy);

        }

      }

    }

    DFS(i, j);

    return total;

  }

  for (let i = 0; i < ROW; i++) {

    for (let j = 0; j < COL; j++) {

      if (maps[i][j] !== 'X') answer.push(island(i, j));

    }

  }

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

}