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

KG·2021년 4월 30일
BFSLv.3알고리즘카카오프로그래머스
3

알고리즘

목록 보기
37/61
post-thumbnail

문제

로봇개발자 "무지"는 한 달 앞으로 다가온 "카카오배 로봇경진대회"에 출품할 로봇을 준비하고 있습니다. 준비 중인 로봇은 2 x 1 크기의 로봇으로 "무지"는 "0"과 "1"로 이루어진 N x N 크기의 지도에서 2 x 1 크기인 로봇을 움직여 (N, N) 위치까지 이동 할 수 있도록 프로그래밍을 하려고 합니다. 로봇이 이동하는 지도는 가장 왼쪽, 상단의 좌표를 (1, 1)로 하며 지도 내에 표시된 숫자 "0"은 빈칸을 "1"은 벽을 나타냅니다. 로봇은 벽이 있는 칸 또는 지도 밖으로는 이동할 수 없습니다. 로봇은 처음에 아래 그림과 같이 좌표 (1, 1) 위치에서 가로방향으로 놓여있는 상태로 시작하며, 앞뒤 구분없이 움직일 수 있습니다.

로봇이 움직일 때는 현재 놓여있는 상태를 유지하면서 이동합니다. 예를 들어, 위 그림에서 오른쪽으로 한 칸 이동한다면 (1, 2), (1, 3) 두 칸을 차지하게 되며, 아래로 이동한다면 (2, 1), (2, 2) 두 칸을 차지하게 됩니다. 로봇이 차지하는 두 칸 중 어느 한 칸이라도 (N, N) 위치에 도착하면 됩니다.

로봇은 다음과 같이 조건에 따라 회전이 가능합니다.

위 그림과 같이 로봇은 90도씩 회전할 수 있습니다. 단, 로봇이 차지하는 두 칸 중, 어느 칸이든 축이 될 수 있지만, 회전하는 방향(축이 되는 칸으로부터 대각선 방향에 있는 칸)에는 벽이 없어야 합니다. 로봇이 한 칸 이동하거나 90도 회전하는 데는 걸리는 시간은 정확히 1초 입니다.

"0"과 "1"로 이루어진 지도인 board가 주어질 때, 로봇이 (N, N) 위치까지 이동하는데 필요한 최소 시간을 return 하도록 solution 함수를 완성해주세요.

제한

  • board의 한 변의 길이는 5 이상 100 이하입니다.
  • board의 원소는 0 또는 1입니다.
  • 로봇이 처음에 놓여 있는 칸 (1, 1), (1, 2)는 항상 0으로 주어집니다.
  • 로봇이 항상 목적지에 도착할 수 있는 경우만 입력으로 주어집니다.

입출력 예시

boardresult
[[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

풀이

2020 카카오 블라인드 테스트에서 출제된 문제이다. 최단 경로로 목적지까지 가는 문제이기 때문에 BFS 알고리즘을 이용해 접근할 수 있다. 하지만 로봇이 회전하는 경우가 추가되었으므로 이것까지 고려하여 BFS 탐색을 해야 한다.

로봇의 회전

위에서 두 번째 사진을 보면 로봇은 두 칸을 점유할 수 있다. 이 두 칸을 방향에 맞춰 각각 '왼쪽'과 '오른쪽'이라고 하자. 또한 로봇은 각 칸을 기준으로 하여 90도 회전을 할 수 있다. 이때 회전하려는 방향에 벽이 있는 경우엔 회전을 할 수 없다. 만약 회전 경로에 벽이 모두 없다고 가정한다면 로봇은 다음과 같이 회전이 가능하다.

  1. 왼쪽칸을 기준으로 위로 회전
  2. 왼쪽칸을 기준으로 아래로 회전
  3. 오른쪽칸을 기준으로 위로 회전
  4. 오른쪽칸을 기준으로 아래로 회전

따라서 현재 위치를 기준으로 각각의 회전이 끝난 경로를 모두 고려하여 BFS 탐색을 수행하여 최단 경로를 찾아야 한다. 먼저 로봇의 회전 후 위치를 반환하는 함수를 구현해보자.

해당 함수는 BFS 로직 내부에서 현재 위치를 인자로 전달받아 연산을 수행할 것이다. 이때 현재 위치 역시 '왼쪽'과 '오른쪽' 칸으로 구별되기 때문에 이를 left와 right라고 하자. 또한 주어진 이동 범위는 2차원 배열이기 때문에 left와 right는 모두 [x좌표, y좌표]의 형태를 취하고 있다.

먼저 회전하는 경우 외에 로봇의 기본 이동을 고려하자. 로봇은 회전을 하지 않고도 상하좌우 4가지 방향으로 이동할 수가 있다. 따라서 이에대한 4가지 경로를 적용하기 위해 회전방향 좌표 배열을 하나 만들어주자. 4가지 경로를 적용 후에 주어진 이동 범위 board를 확인해 벽이 있는지 없는지 체크하여 벽이 없다면 해당 경로를 결과값에 추가하도록 하자.

const getNextPosition = (left, right, board) => {
  // X와 Y좌표 상수값 지정 (주어진 배열에서 둘의 위치에 주의하자)
  const X = 1; const Y = 0;
  // 로봇의 이동/회전이 끝난 후의 좌표를 저장할 배열
  const result = [];
  // 각 이동 경로 좌표 (상, 하, 좌, 우)
  const moves = [ [-1, 0], [1, 0], [0, -1], [0, 1] ];
  
  for(const move of moves) {
    // dy, dx는 각각 상,하,좌,우로 이동을 적용하기 위한 값
    const [dy, dx] = move;
    // 전달받은 left와 right에 이동방향 적용
    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]);
    }
  }
  ...
}

또 위에서 언급한 회전 경로 역시 모두 고려하여 값을 추가해주자. 역시 회전 경로를 적용하기 위한 좌표 배열 toward를 선언하고 전체 좌표를 확인해 벽이 있는지 없는지 체크하여 벽이 없는 경우 해당 좌표를 result에 푸시하도록 하자.

const getNextPosition = (left, right, board) => {
  ...
  
  // 로봇은 한 점을 기준으로 회전하기 때문에
  // 회전 경로 파악을 위해서는 현재 로봇의 위치를 기준으로
  // 가로 방향이면 위쪽과 아래쪽, 세로 방향이면 왼쪽과 오른쪽이
  // 모두 벽이 없는 상태여야 회전이 가능하다.
  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;
}

위 함수를 통해 현재 로봇의 좌표를 전달하면 이동 및 회전을 모두 적용한 위치 좌표를 배열값으로 전달받을 것이다. 이 값을 활용해 BFS 탐색을 구현하도록 하자.

BFS를 이용한 최단 경로

일반적인 최단 경로를 구하는 BFS 탐색과 크게 다르지 않다. 다만 이동 경로를 위에서 구현한 함수를 통해 구해주어야 하는 것과 이미 탐색한 경로인지 아닌지를 잘 체크해주어야 한다.

먼저 BFS 탐색을 위한 queue를 초기화 해주자. 이때 최단 경로를 계산해주기 위해 좌표값 뿐만 아니라 deps도 같이 넣어주어 거리를 계산할 수 있도록 초기화가 필요하다. 그리고 회전 경로를 계산해주기 위한 전체 탐색 범위 배열도 만들어주자. 이때 시작 좌표가 (1,1), (1,2)와 같이 시작하므로 인덱스와의 차이를 고려함과 동시에 각 한 칸씩 이동할 때 기존 좌표를 초과하는 경우 역시 고려해주기 위해 기존에 주어진 board 배열의 크기보다 2만큼 더 큰 배열로 만들어주자.

const N = board.length;
// [ [ 왼쪽좌표, 오른쪽좌표, deps ] ] 구조의 queue
const queue = [ [ [1,1], [1,2], 0 ] ];
// board.length + 2 크기의 2차원 배열 생성
// 초기 상태는 모두 1(벽)으로 초기화
const new_board = new Array(N+2).fill().map(_ => new Array(N+2).fill(1));
// board 값에 해당하는 좌표는 다시 기존 board 값으로 갱신
for(let i = 0; i < N; i++) {
  for(let j = 0; j < N; j++) {
    new_board[i+1][j+1] = board[i][j];
  }
}

참고로 자바스크립트는 이미 구현이 완료된 queue 라이브러리가 없다. 따라서 배열을 이용해서 FIFO 원칙만 고수하도록 shift() 함수를 이용하여 야매(?) 구현을 하는데, 이 방식은 다른 언어의 queue 자료구조와 달리 시간 복잡도가 더 크다. 때문에 만약 데이터의 크기가 매우 큰 경우엔 이 방식으로는 종종 시간복잡도를 초과하는 경우가 발생한다. 이때는 따로 queue 자료구조를 직접 구현해서 풀어야 한다... 관련해서는 자료구조 시리즈의 게시글을 참고하자.

문제의 조건에 따르면 BFS가 종료되는 시점은 왼쪽 또는 오른쪽 어느 하나라도 목적지에 도달하는 경우가 될 것이다. 이때 목적지는 주어진 board의 가장 마지막 지점이고, 이는 좌표로 표현하면 N이 board의 크기일때 (N, N) 지점과 같다.

관련해서 방문 여부를 체크할 변수 visit 역시 필요하다. 보통 true 또는 false 값으로 방문여부를 체크하지만 여기서는 좌표값을 기준으로 체크하도록 하자. 주의해야 할 점은 로봇이 두 개의 좌표를 동시에 점유하기 때문에 고유한 좌표값을 만들어주어야 한다. 따라서 로봇의 현재 왼쪽좌표와 오른쪽좌표를 문자열로 더해준 값을 사용하도록 하자. 각 경로의 좌표는 모두 다르기 때문에 왼쪽좌표와 오른쪽좌표를 더한 문자열의 값은 모두 고유하다고 할 수 있다. 예를 들어,

  • 왼쪽좌표 (1,1), 오른쪽좌표 (1,2) => "1112"
  • 왼쪽좌표 (1,2), 오른쪽좌표 (1,1) => "1211"

위 두가지 사례는 로봇의 배치된 모습은 동일하지만 서로의 좌표가 다르기 때문에 서로 다른 값으로 정확히 인식할 수 있다. 각 좌표값이 모두 고유하기 때문에 이를 Set 자료구조를 이용해 중복체크를 하여 방문여부를 검사할 수 있다.

// 목적지의 좌표 문자열값은 "NN"이 될 것
const goal = N + '' + N;
// 초기 점유 좌표 문자열은 "1112"
const visit = new Set(["1112"]);

이제 BFS 로직을 돌릴 환경을 모두 조성했다. 따라서 BFS 로직을 통해 최단 경로를 구해주도록 하자.

while(queue.length) {
  // FIFO 라는 것에 유의하자!
  const [left, right, count] = queue.shift();
  
  // 로봇의 양 좌표 중 하나라도 목적지에 도달하면 종료
  if(left.join('') === goal || right.join('') === goal) return count;
  
  // 로봇의 다음 경로를 모두 구해서
  const next_position = getNextPosition(left, right, new_board);
  // 구한 경로를 방문할 수 있는지 없는지를 체크
  for(const next of next_position) {
    const [next_left, next_right] = next;
    // 키값은 양 좌표를 문자열로 더한 값
    const key = next_left.join('') + next_right.join('');
    // 아직 방문하지 않았다면 큐와 visit에 삽입
    if(!visit.has(key)) {
      queue.push([next_left, next_right, count+1]);
      visit.add(key);
    }
  }
}

전체코드

두 좌표를 동시에 점유한다는 점과 회전요소까지 고려해야 하는 점이 다소 까다롭게 다가오긴 하지만, 차근차근 접근한다면 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://programmers.co.kr/learn/courses/30/lessons/60063

profile
KG
개발잘하고싶다
이전 포스트

[프로그래머스] LV.3 다단계 칫솔 판매 (JS)

다음 포스트

[프로그래머스] LV.3 불량 사용자 (JS)

0개의 댓글