[프로그래머스] 무인도 여행 / JavaScript / Level 2

🚩문제 주소

📄 풀이

☀️키워드 - 그래프 탐색

땅이 X가 아니고 한번도 방문한 적이 없다면 bfs함수를 호출합니다.

bfs 함수

현재 위치를 큐에 넣어줍니다. 그리고 현재 위치의 숫자를 더해주고 방문체크를 합니다.
현재 위치에서 상, 하, 좌, 우 네 방향을 확인하여 제한구간을 넘지 않고, 방문한 적이 없으며, X인 땅이 아니라면 방문 확인을 하고 확인한 위치의 숫자를 더해줍니다.
그리고 큐에 확인한 위치를 넣어줍니다.

큐가 비어서 반복이 종료된다면 지금까지 더해진 수를 결과 배열에 넣어줍니다.

모든 과정을 마치고 나온 결과배열의 길이가 0이라면 [-1]를 반환합니다.

아니라면 결과배열을 오름차순으로 정렬한 뒤 반환합니다.

👨‍💻 코드

function solution(maps) {
  const result = [];
  const [R, C] = [maps.length, maps[0].length];
  const visited = Array.from({ length: R }, () => Array(C).fill(0));
  const move = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  const bfs = (a, b) => {
    let cnt = 0;
    const q = [[a, b]];
    cnt += parseInt(maps[a][b]);
    visited[a][b] = 1;

    while (q.length) {
      const [r, c] = q.shift();
      for (let i = 0; i < 4; i++) {
        const nr = r + move[i][0];
        const nc = c + move[i][1];
        if (nr >= 0 && nc >= 0 && nr < R && nc < C && 
            !visited[nr][nc] && maps[nr][nc] !== "X") {
          visited[nr][nc] = 1;
          cnt += parseInt(maps[nr][nc]);
          q.push([nr, nc]);
        }
      }
    }
    result.push(cnt);
  };

  for (let i = 0; i < R; i++) {
    for (let j = 0; j < C; j++) {
      if (!visited[i][j] && maps[i][j] !== "X") bfs(i, j);
    }
  }

  if (result.length === 0) return [-1];

  return result.sort((a, b) => a - b);
}