[콭] 무인도 여행 - DFS

무인도 여행

문제

X가 아닌 matrix 블럭의 상하좌우를 옮겨다니며 연결된 블록들의 값의 합을 구하고 오름차순으로 정렬하라.

접근방법

DFS
maps에 다녀간 표시를 하는 법
1. string 배열=>이차원 배열로 변경 후 값을 대입
2. substring으로 문자열을 입맛대로 자르고 조합

javascript 코드

function solution(maps) {
  var answer = [];

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

  const row = maps.length; //x 5 i
  const col = maps[0].length; //y 4 j
  
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      
      if (maps[i][j] === "X") continue;
      let move = maps[i][j] * 1;//분리된 무인도 각 칸의 합 세기 시작
        
      maps[i] = maps[i].substring(0, j) + "X" + maps[i].substring(j + 1);//방문 표시
        
      let visit = [[i, j]];
        
      while (visit.length) {
        let [x, y] = visit.pop();
          
        for (let k = 0; k < 4; k++) {
          const curX = x + dx[k];
          const curY = y + dy[k];
            
          //matrix를 벗어나거나 X면 아웃
          if (curX < 0 || curX >= row || curY < 0 || curY >= col) continue;
          if (maps[curX][curY] === "X") continue;
            
          visit.push([curX, curY]);
          move += maps[curX][curY] * 1;
            
          //방문표시
          maps[curX] = maps[curX].substring(0, curY) +"X" + maps[curX].substring(curY + 1);
       
        }
      } 
      answer.push(move);
    }
  } 
  return answer.length ? answer.sort((a, b) => a - b) : [-1]; ;
} 

주의

나는 항상 col-row, x-y 좌표를 헷갈려한다. 이번 기회에 정신차리자!