[Programmers] 무인도 여행 - Javascript

INDEX

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

프로그래머스

 

 

Solution

그래프 문제는 보통 DFS 아니면 BFS 로 푸는 문제입니다.

이 문제 같은 경우에는 1부터 9까지의 자연수 블록이 연결된 영역을 계속 찾다가 "X" 혹은 벽을 만나면 탐색을 종료하는 알고리즘이기 때문에 DFS 를 사용할 수 있습니다.

 

주의해야 할 포인트는, 방문한 무인도(노드)는 꼭 다시 방문하지 말아야 한다는 점입니다. 왜냐하면 이미 탐색된 무인도는 연결된 영역이 존재한다는 것이 분명하기 때문에 다시 방문해도 의미가 없습니다. 

 

const moveRow = [1, -1, 0, 0];
const moveCol = [0, 0, 1, -1];

상, 하, 좌, 우로 움직일 수 있기 때문에 좌표 이동 값을 설정해주었습니다.

많은 분들이 x, y 로 그래프에서 좌표를 표현하시는데 저는 행과 열로 표현하는게 더 편하더라구요.

 

* 이게 왜 상 하 좌 우 로 갈 수 있는 이동 좌표값인지 모르시는 분들을 위해 아래 코드를 추가했습니다.

for (let i = 0; i < 4; i++) {
    let nRow = 현재 행 + moveRow[i];
    let nCol = 현재 열 + moveCol[i];
}
//위 반복문을 실행하면 모든 상, 하, 좌, 우 방향으로 1칸씩 이동을 해본 상태임을 알 수 있습니다.

maps = maps.map((m) => m.split(""));
//["X591X", "X1X5X", "X231X", "1XXX1"] => 
//[["X","5","9","1","X"], ["X","1","X","5","X"], ["X","2","3","1","X"], ["1","X","X","X","1"]]

let answer = [];
for (let row = 0; row < maps.length; row++) {
    for (let col = 0; col < maps[0].length; col++) {
      //모든 무인도를 탐색합니다.
      let sum = 0;
      const q = [[row, col]];
      while (q.length !== 0) {
        const [row_, col_] = q.shift();

        if (maps[row_][col_] !== "visited" && maps[row_][col_] !== "X") { //방문했던 무인도나 X표시가 있는 곳은 탐색하지 않습니다.
          sum += Number(maps[row_][col_]);
          maps[row_][col_] = "visited";

          for (let i = 0; i < 4; i++) {
            let nRow = row_ + moveRow[i];
            let nCol = col_ + moveCol[i];
            if (maps[nRow] && maps[nRow][nCol]) q.push([nRow, nCol]); //다음 무인도가 탐색 가능한 곳인지 확인 후 스택에 추가합니다.
          }
        }
      }
      if (sum > 0) answer.push(sum);
    }
}

마지막으로 정답은 오름차순이고 무인도가 없다면 -1을 담아서 return 합니다.

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

 

전체코드

function solution(maps) {
  const moveRow = [1, -1, 0, 0];
  const moveCol = [0, 0, 1, -1];

  maps = maps.map((m) => m.split(""));
  let answer = [];
  for (let row = 0; row < maps.length; row++) {
    for (let col = 0; col < maps[0].length; col++) {
      //모든 무인도를 탐색합니다.
      let sum = 0;
      const q = [[row, col]];
      while (q.length !== 0) {
        const [row_, col_] = q.shift();

        if (maps[row_][col_] !== "visited" && maps[row_][col_] !== "X") { //방문했던 무인도나 X표시가 있는 곳은 탐색하지 않습니다.
          sum += Number(maps[row_][col_]);
          maps[row_][col_] = "visited";

          for (let i = 0; i < 4; i++) {
            let nRow = row_ + moveRow[i];
            let nCol = col_ + moveCol[i];
            if (maps[nRow] && maps[nRow][nCol]) q.push([nRow, nCol]); //다음 무인도가 탐색 가능한 곳인지 확인 후 스택에 추가합니다.
          }
        }
      }
      if (sum > 0) answer.push(sum);
    }
  }
}
return answer.length > 0 ? answer.sort((a, b) => a - b) : [-1];