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

풀이 과정

DFS
1. visited 배열 생성
2. 각 칸에 대해 반복하면서 DFS 탐색
3. 방문한 칸의 값을 더하다가 이어진 곳이 없으면 결과 배열에 추가
4. 더이상 방문할 칸이 없으면 반복 빠져나오기
5. 배열이 비었으면 -1이 담긴 배열 리턴

코드

function solution(maps) {
  const result = [];
  maps = maps.map((e) => [...e]);
  const [h, w] = [maps.length, maps[0].length];
  const visited = Array(h)
    .fill(0)
    .map((_) => Array(w).fill(false));
  const DIR = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ]; // 오른 아래 왼 위
  for (let i = 0; i < h; ++i) {
    for (let j = 0; j < w; ++j) {
      if (visited[i][j] || maps[i][j] === 'X') continue;
      const q = [[i, j]];
      let cnt = 0;
      while (q.length) {
        const [y, x] = q.pop();
        visited[y][x] = true;
        cnt += Number(maps[y][x]);
        for (let k = 0; k < 4; ++k) {
          const ny = y + DIR[k][0];
          const nx = x + DIR[k][1];
          if (ny < 0 || ny >= h || nx < 0 || nx >= w) continue;
          if (visited[ny][nx] || maps[ny][nx] === 'X') continue;
          q.push([ny, nx]);
          visited[ny][nx] = true;
        }
      }
      result.push(cnt);
    }
  }
  return result.length ? result.sort((a, b) => a - b) : [-1];
}

🦾

오랜만에 해보려니 DFS 까먹은 거 아닌가 싶었는데 막상 풀어보니 금방 풀 수 있었다.