[CodeKata] 프로그래머스: 12.19(일), 블록 이동하기

🥋 Oooth More!! (Level 3) 

 

🧮 풀이

check배열로 방문을 기록하면서 DFS로 풀어보려 했으나, 방법이 모호했으며 무엇보다 회전하는 경우를 고려하기가 힘들었다.

이번에도 눈물을 머금고... 모범답안의 힘을 빌리기로 했다!

 

🖇 리뷰

최단경로를 탐색하는 문제이므로 BFS를 사용해야 한다. 이 때, 회전까지 고려해야하는 부분이 어려웠는데 모범답안으로 학습해보았다.

function solution (board) {
  const N = board.length;
  const goal = N + '' + N;
  const queue = [ [ [1,1], [1,2], 0 ] ];
  const visit = new Set(["1112"]);
  
  const new_board = new Array(N+2).fill().map(_ => new Array(N+2).fill(1));
  for(let i = 0; i < N; i++) {
    for(let j = 0; j < N; j++) {
      new_board[i+1][j+1] = board[i][j];
    }
  }
  
  while(queue.length) {
    const [left, right, count] = queue.shift();
    
    if(left.join('') === goal || right.join('') === goal) return count;
    
    const nextPosition = getNextPosition(left, right, new_board);
    for(const next of nextPosition) {
      const [next_left, next_right] = next;
      const key = next_left.join('') + next_right.join('');
      if(!visit.has(key)) {
        queue.push([next_left, next_right, count+1]);
        visit.add(key);
      }
    }
  }
}

const getNextPosition = (left, right, board) => {
  const result = [];
  const X = 1, Y = 0;
  const moves = [ [-1,0], [1, 0], [0,-1], [0,1] ];
  
  for(const move of moves) {
    const [dy, dx] = move;
    const next_left = [ left[Y]+dy, left[X]+dx ];
    const next_right = [ right[Y]+dy, right[X]+dx ];
    
    if(board[next_left[Y]][next_left[X]] === 0 &&
       board[next_right[Y]][next_right[X]] === 0) {
      result.push([next_left, next_right]);
    }
  }
  
  const toward = [-1, 1];
  
  if(left[Y] === right[Y]) {
    for(const dy of toward) {
      if(board[left[Y]+dy][left[X]] === 0 &&
         board[right[Y]+dy][right[X]] === 0) {
        result.push([ left, [ left[Y]+dy, left[X] ] ]);
        result.push([ [ right[Y]+dy, right[X] ], right ]);
      }
    }
  } else {
    for(const dx of toward) {
      if(board[left[Y]][left[X]+dx] === 0 &&
         board[right[Y]][right[X]+dx] === 0) {
        result.push([ [left[Y], left[X]+dx ], left ]);
        result.push([ right, [ right[Y], right[X]+dx ] ]);
      }
    }
  }                  
  
  return result;
}

* https://velog.io/@longroadhome/%ED%94%84%EB%A1%9C%EA%B7%B8%EB%9E%98%EB%A8%B8%EC%8A%A4-LV.3-%EB%B8%94%EB%A1%9D-%EC%9D%B4%EB%8F%99%ED%95%98%EA%B8%B0-JS

 

1. BFS를 위한 준비

• N은 board 길이로 빈번히 사용될 값이다. goal은 목표좌표로, "NN" 형태이다. (N-1이 아닌 이유는, 아래 new_board 확장때문!)
• 또, BFS를 위한 queue 배열을 선언하고, [왼쪽, 오른쪽, count] 형태로 초기값으로 넣어준다. visit은 방문한 케이스를 관리하는 Set로 "x1x2y1y2"를 담는다.
• 로봇 좌표가 [[0,0], [0,1]] 이 아닌 이유가 이 new_board(확장된 board) 에 이유가 있다. 로봇의 이동 및 회전이 board를 벗어날 때 에러를 쉽게 관리하기 위해, board 테두리를 1(벽)으로 감싼 new_board 를 활용하는 것이다. new_board의 [i+1][j+1] 값은 기존 board[i][j]와 같다.
• queue가 존재하는 동안 while 반복문을 시행한다. 현재값을 [left, right, count]로 빼고, left나 right가 정답(goal)이면 count를 반환한다. 아니라면, nextPosition을 queue에 넣어줘야 한다. 여기서 getNextPosition() 함수를 한 번 면밀히 짚고 넘어가자!

 

2. getNextPosition()

• 로봇의 이동(상하좌우) 및 회전을 했을 때, 이동 가능한 좌표들을 반환하는 함수다. 인자는, left, right, board 3가지를 받는다.
• 최초 설정시, [y1, x1], [y2, x2] 형태로 선언했다. 그렇기에, Y좌표는 0번째, X좌표는 1번째로 상수를 설정해놓는다.
• result는 이동/회전이 가능한 좌표들을 담을 배열이다. 먼저, 상하좌우 좌표를 next_left, next_right로 만들고 여기의 board 값이 0이라면 이동이 가능하므로 result에 push 해놓는다.
• 다음은 회전 경우이다. 로봇이 가로방향 이라면 위/아래, 세로방향 이라면 왼/오른쪽이 모두 벽이 없어야만한다.
• toward는 -(위 혹은 왼쪽), +(아래 혹은 오른쪽) 2가지 경우다. 또한, left[Y], right[Y] 가 같으면 가로, 다르다면 세로의 경우이다.
• 가로일 땐, toward 변화량을 dy(세로)로 잡는다. 그 때, 위 혹은 아래가 벽이 아니라면, 왼쪽 및 오른쪽 좌표를 기준으로 각각 상향 혹은 하양한 좌표들을 result에 push 한다. (첫 번째는 [left 고정, left 위 혹은 아래], 두 번째는 [right 위 혹은 아래 , right 고정])
• 세로일 땐, toward 변화량을 dx(가로)로 잡는다. 그 떄, 왼쪽 혹은 오른쪽이 벽이 아니라면, 위 및 아래 좌표 기준으로 각각 좌향 혹은 우향한 좌표들을 result에 push 한다. (첫 번째는 [left 왼쪽 혹은 오른쪽, left], 두 번째는 [right, right 왼쪽 혹은 오른쪽])

 

3. 다음 경로들 BFS로 계산

• 다시 while 반복문에서, nextPosition은 getNextPosition() 함수로 획득한 현재 좌표에서 갈 수 있는 다음 좌표들의 배열이다.
• 이 nextPosition 들을 순회하면서, visit에 포함되있는지 확인한다. 없다면, 이를 queue에 넣어주고 visit에도 추가한다.