[구현] 보드 게임

보드 게임

문제

N * N의 크기를 가진 보드판 위에서 게임을 하려고 합니다. 게임의 룰은 다음과 같습니다.

1. 좌표 왼쪽 상단(0, 0)에 말을 놓는다.
2. 말은 상, 하, 좌, 우로 이동할 수 있고, 플레이어가 조작할 수 있다.
3. 조작의 기회는 딱 한 번 주어진다.
4. 조작할 때 U, D, L, R은 각각 상, 하, 좌, 우를 의미하며 한 줄에 띄어쓰기 없이 써야 한다.
5. 한 번 움직일 때마다 한 칸씩 움직이게 되며, 그 칸 안의 요소인 숫자를 획득할 수 있다.
6. 방문한 곳을 또 방문해도 숫자를 획득할 수 있다.
7. 보드 밖을 나간 말은 OUT 처리가 된다.
8. 칸 안의 숫자는 0 또는 1이다.
9. 획득한 숫자를 합산하여 숫자가 제일 큰 사람이 이기게 된다.

보드판이 담긴 board와 조작하려고 하는 문자열 operation이 주어질 때, 말이 해당 칸을 지나가면서 획득한 숫자의 합을 구하는 함수를 작성하세요.

입력

인자 1: board

• number 타입의 2차원 배열
• 2 <= board.length <= 1,000
• 예: [ [0, 0, 1], [1, 0, 1], [1, 1, 1] ]

인자 2: operation

• string 타입의 대문자 영어가 쓰여진 문자열
• 1 <= operation.length <= board.length * 2
• U, L, D, R 이외의 문자열은 없습니다.

출력

• Number 타입을 반환해야 합니다.

주의사항

• 만약, 말이 보드 밖으로 나갔다면 즉시 OUT 을 반환합니다.

입출력 예시

const board1 = [
  [0, 0, 0, 1],
  [1, 1, 1, 0],
  [1, 1, 0, 0],
  [0, 0, 0, 0]
]
const output1 = boardGame(board1, 'RRDLLD');
console.log(output1); // 4


const board2 = [
  [0, 0, 1],
  [1, 1, 1],
  [1, 0, 0]
]
const output2 = boardGame(board2, 'UUUDD');
console.log(output2); // 'OUT'

const board3 = [
  [0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0]
]
const output3 = boardGame(board3, 'DDRRRUDUDUD');
console.log(output3); // 0

문제풀이

function boardGame(board, operation) {
  // 이동 방향에 대한 LOOK UP TABLE 정의
  const DIRECTION = {
    'U': [-1, 0], 'D': [1, 0], 'L': [0, -1], 'R': [0, 1]
  }
  let [y, x] = [0, 0];
  // operation 문자열을 순회하면서 위치 이동
  // reduce 함수로 score 누적
  return operation.split('').reduce((score, dir) => {
    [y, x] = [y + DIRECTION[dir][0], x + DIRECTION[dir][1]];
    // 보드 밖으로 이동한 경우 'OUT' 반환
    // 그렇지 않으면 현재 위치의 값을 score에 누적
    return y < 0 || y >= board.length || x < 0 || x >= board.length ? 'OUT' : score + board[y][x];
  }, 0);
}

/*
function boardGame(board, operation) {
  const DIRECTION = {
    'U': [-1, 0], // 상
    'D': [1, 0], // 하
    'L': [0, -1], // 좌
    'R': [0, 1] // 우
  }
  const BOARD_SIZE = board.length;

  // 행과 열의 범위가 유효한지 검사하는 함수
  function isValid(y, x) {
    return (0 <= y && y < BOARD_SIZE && 0 <= x && x < BOARD_SIZE);
  }

  let score = 0;
  let y = 0;
  let x = 0;

  // 주어진 operation 문자열에서 한 글자씩 읽어들여 이동을 수행
  for (let i = 0; i < operation.length; i++) {
    const direction = DIRECTION[operation[i]];
    y += direction[0];
    x += direction[1];

    // 만약 보드 범위를 벗어나면 "OUT"을 반환하고 함수 종료
    if (isValid(y, x) === false) {
      return "OUT";
    }

    score += board[y][x]; // 이동한 위치의 값 더하기
  }

  return score; // 총합 반환
}
*/

두 코드는 기능적으로 동일합니다. 하지만 "LOOK UP TABLE"을 사용한 코드는 조건문을 추상화하여 코드를 더욱 간결하게 만들 수 있습니다. 이로 인해 더 빠르게 실행될 가능성이 높습니다. 그러나 실제로 두 코드 간의 속도 차이는 상대적으로 미미할 것으로 예상됩니다.

두 코드의 시간 복잡도는 모두 O(n)입니다. 이는 보드 크기와 조작 문자열의 길이에 비례하며, 보드 크기와 조작 문자열의 증가에 따라 선형적으로 증가합니다.

 

LOOK UP TABLE
LOOK UP TABLE(또는 LUT)은 미리 계산된 값을 담고 있는 테이블을 사용하여 계산을 수행하는 기법입니다. 
이는 프로그램의 성능을 향상시키기 위해 사용됩니다. 예를 들어, 매번 sin() 또는 cos() 함수를 호출하여 
삼각 함수 값을 계산하면 비용이 많이 드는 작업입니다. 
하지만 사전에 삼각 함수 값 테이블을 계산하면 값을 직접 참조하여 계산할 수 있으므로 계산 비용이 크게 줄어듭니다.

위의 게임 문제를 풀 때, 매번 조건문으로 현재 위치가 유효한지 확인하는 것보다, 
미리 방향의 값을 저장해두고 이를 통해 이동할 위치를 계산하는 것이 더 효율적입니다. 
이렇게 계산된 값을 배열로 묶어서 미리 저장해 둔 것을 LOOK UP TABLE이라고 합니다. 
따라서 위의 코드에서 DIR 객체는 LOOK UP TABLE의 일종입니다.

레퍼런스 코드

function boardGame(board, operation) {
  // 방향에 대한 LOOK UP TABLE을 정의합니다.
  const DIR = {
    'U': [-1, 0],
    'D': [1, 0],
    'L': [0, -1],
    'R': [0, 1]
  }
  // board 배열의 길이를 변수에 저장합니다.
  const LEN = board. length;
  // 함수 isValid를 정의합니다. y와 x의 값이 board 배열의 범위를 벗어나는지 확인합니다.
  const isValid = (y, x) => 0 <= y && y < LEN && 0 <= x && x < LEN;

  let Y = 0;
  let X = 0;
  let score = 0;
  // operation 문자열에서 한 문자씩 꺼내어 처리합니다.
  for (let i = 0; i < operation.length; i++) {
    // 방향 문자에 대응하는 이동량을 DIR에서 찾아 더합니다.
    const [dY, dX] = DIR[operation[i]];
    Y += dY;
    X += dX;
    // 새로운 위치가 board 배열의 범위를 벗어나면 'OUT'을 반환하고 함수를 종료합니다.
    if (isValid(Y, X) === false) return 'OUT';
    // 새로운 위치의 값을 score에 더합니다.
    score += board[Y][X];
  }
  // 최종 score를 반환합니다.
  return score;
};