[프로그래머스 lev3/JS] 블록 이동하기

문제 출처

프로그래머스 lev3 - 블록 이동하기

나의 풀이 (실패)

다른 풀이

나는 회전의 경우의 수를 일일이 구하다가 머리가 뜨거워졌다.

아래 풀이에서는 회전의 경우의 수를 굉장히 간단하게 구현했다. 하나하나 직접 모든 방향을 고려하는 게 아니라 일반화를 해서 구현했다.

• 로봇이 수평일 경우, 회전하려면 위/아래에 장애물이 없어야 한다.
• 로봇이 수직일 경우, 회전하려면 좌/우에 장애물이 없어야 한다.

이때 [-1, 1] 배열을 만들어서 방향전환 가능 여부와 방향전환을 한번에 처리한다.
수평이면 해당 배열의 값을 y좌표에만 더해주면 되고,
수직이면 해당 배열의 값을 x좌표에만 더해주면 된다.

그리고 회전된 nextPosition 좌표의 경우도 어떻게 구하냐면,

• 수직일 때 회전이동한다면,
  오른쪽 좌표가 회전이동한다면, 왼쪽 좌표의 x좌표를 사용하고
  왼쪽 좌표가 회전이동한다면, 오른쪽 좌표의 x좌표를 사용한다.
• 수평일 때 회전이동한다면,
  오른쪽 좌표가 회전이동한다면, 왼쪽 좌표의 y좌표를 사용하고
  왼쪽 좌표가 회전이동한다면, 오른쪽 좌표의 y좌표를 사용한다.

이렇게 다음 좌표를 구하는 로직을 구현했다면 그 다음은 기존에 완전탐색을 구현하는 것과 같다. 아래 풀이는 bfs로 구현했는데,

해당 position에서 다음에 갈 수 있는 좌표들의 경우의 수를 nextPosition에 삽입해둔뒤 이들에 대해 방문 가능 여부를 체크한다.

방문 가능 여부를 체크할 때 set 메서드를 사용했다. 여기도 사실 내가 넘기 어려운 벽이었다. 왜냐면 나는 동안 방문여부 체크를 할 때 주어진 배열과 똑같은 형태로만 하려는 강박 같은 게 있었으니까.

어쨌든 중복이 아니라면, 즉 방문이 가능하다면
queue에 삽입하고 방문 처리를 해준다.

목표 지점에 도착했다면 count를 return 처리해준다.

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
}

console.log(
  solution([
    [0, 0, 0, 1, 1],
    [0, 0, 0, 1, 0],
    [0, 1, 0, 1, 1],
    [1, 1, 0, 0, 1],
    [0, 0, 0, 0, 0],
  ])
); // 7

위 코드에서 shift/push는 O(n)이므로 이를 O(1)로 변경하기 위해 직접 Queue를 만들어서 풀면 다음과 같다. (물론 여기서는 queue의 shift/push 보다는 다른 로직이 더 무거워서 큰 차이는 없는 것 같다.)

class Queue {
  constructor(array){
    this.array = array ? array : []
    this.tail = array ? array.length : 0
    this.head = 0 
  }
  enqueue = (element) => this.array[this.tail++] = element 
  dequeue = () => {
    if(this.tail == this.head) return undefined 

    let element = this.array[this.head]
    delete this.array[this.head++]
    return element 
  }
  size = () => this.array.length
}
// function Queue(array){
//   this.array = array ? array : []
//   this.tail = array ? array.length : 0
//   this.head = 0 
// }
// Queue.prototype.enqueue = function(element){
//   return this.array[this.tail++] = element 
// }
// Queue.prototype.dequeue = function(){
//   if(this.tail == this.head) return undefined 

//   let element = this.array[this.head]
//   delete this.array[this.head++]
//   return element 
// }
// Queue.prototype.size = function(){
//   return this.array.length 
// }

function solution (board) {
  const N = board.length
  const goal = N + '' + N
  // const queue = [ [ [1,1], [1,2], 0 ] ]
  const queue = new 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.size()) {
    const [left, right, count] = queue.dequeue()
    
    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.enqueue([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])
      result[result.length] = [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[result.length] = [ left, [ left[Y]+dy, left[X] ] ]
        // result.push([ [ right[Y]+dy, right[X] ], right ])
        result[result.length] = [ [ 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[result.length] = [ [left[Y], left[X]+dx ], left ]
        // result.push([ right, [ right[Y], right[X]+dx ] ])
        result[result.length] = [ right, [ right[Y], right[X]+dx ] ]
      }
    }
  }                  
  
  return result
}

다른 풀이 2

더 빠르다.

function solution(map) {
  const n = map.length,
    dx = [0, 0, 1, -1],
    dy = [1, -1, 0, 0],
    rowToColDx = [-1, -1, 0, 0],
    rowToColDy = [0, 1, 0, 1],
    colToRowDx = [0, 1, 0, 1],
    colToRowDy = [0, 0, -1, -1],
    q = [
      [0, 0, 0, 0]
    ],
    visited = [];

  for (let i = 0; i < n; i++) {
    visited.push([]);
    for (let j = 0; j < n; j++) {
      visited[i].push([Infinity, Infinity]);
    }
  }

  visited[0][0][0] = 0;

  let min = Infinity;

  const canGoRight = (x, y, p) => {
    if(p === 0) {
      if(y+2 >= n || map[x][y+1] === 1 || map[x][y+2] === 1)
        return false;
    }else {
      if(y+1 >= n || x+1 >= n || map[x][y+1] === 1 || map[x+1][y+1] === 1)
        return false;
    }
    return true;
  };

  const canGoLeft = (x, y, p) => {
    if(p === 0) {
      if(y-1 < 0 || map[x][y-1] === 1)
        return false;
    }else {
      if(y-1 < 0 || x+1 >= n || map[x][y-1] === 1 || map[x+1][y-1] === 1)
        return false;
    }
    return true;
  };

  const canGoDown = (x, y, p) => {
    if(p === 0) {
      if(x+1 >= n || y+1 >= n || map[x+1][y] === 1 || map[x+1][y+1] === 1)
        return false;
    }else {
      if(x+2 >= n || map[x+1][y] === 1 || map[x+2][y] === 1) {
        return false;
      }
    }
    return true;
  };

  const canGoUp = (x, y, p) => {
    if(p === 0) {
      if(x-1 < 0 || y+1 >= n || map[x-1][y] === 1 || map[x-1][y+1] === 1)
        return false;
    }else {
      if(x-1 < 0 || map[x-1][y] === 1) {
        return false;
      }
    }
    return true;
  };

  const canRotateUp = (x, y) =>
    !(x - 1 < 0 || y + 1 >= n || map[x - 1][y] === 1 || map[x - 1][y + 1] === 1);

  const canRotateDown = (x, y) =>
    !(x + 1 >= n || y + 1 >= n || map[x + 1][y] === 1 || map[x + 1][y + 1] === 1);

  const canRotateRight = (x, y) =>
    !(y + 1 >= n || x + 1 >= n || map[x][y + 1] === 1 || map[x + 1][y + 1] === 1);

  const canRotateLeft = (x, y) =>
    !(y - 1 < 0 || x + 1 >= n || map[x][y - 1] === 1 || map[x + 1][y - 1] === 1);

  const canGoMap = [
    canGoRight,
    canGoLeft,
    canGoDown,
    canGoUp
  ],
    canRotateMap = [
      [
        canRotateUp,
        canRotateUp,
        canRotateDown,
        canRotateDown
      ], [
        canRotateRight,
        canRotateRight,
        canRotateLeft,
        canRotateLeft
      ],
    ],

    deltaMap = [
      [rowToColDx, rowToColDy],
      [colToRowDx, colToRowDy]
    ];

  while (q.length) {
    const [x, y, t, p] = q.shift();

    // 만일 (n,n)에 도착했다면 최소시간을 갱신합니다
    if (
      (x === n - 1 && y === n - 2 && p === 0)
      || (x === n - 2 && y === n - 1 && p === 1)
    ) {
      min = Math.min(min, t);
    }

    // 회전 없이 우좌하상으로 움직일때
    for (let k = 0; k < 4; k++) {
      if (!canGoMap[k](x, y, p)) {
        continue;
      }

      const nx = x + dx[k],
        ny = y + dy[k];

      if (visited[nx][ny][p] > t + 1) {
        visited[nx][ny][p] = t + 1;
        q.push([nx, ny, t + 1, p]);
      }
    }

    for (let k = 0; k < 4; k++) {
      // 가로로 놓인 상황인 경우 세로로 돌려보자
      // 세로로 놓인 상황인 경우 가로로 돌려보자

      if (!canRotateMap[p][k](x, y)) continue;

      const nx = x + deltaMap[p][0][k],
        ny = y + deltaMap[p][1][k],
        _p = p ? 0 : 1;

      if (visited[nx][ny][_p] > t + 1) {
        visited[nx][ny][_p] = t + 1;
        q.push([nx, ny, t + 1, _p]);
      }
    }

  }

  return min;
}

참고

[프로그래머스] LV.3 블록 이동하기 (JS)
[프로그래머스] 2020 KAKAO BLIND RECRUITMENT 블록이동하기