본문 바로가기
Algorithm/문제풀이

[HackerRank] The Bomberman Game (Medium) by javascript

by 썸머워즈 2022. 8. 4.
반응형

▷ 문제 : The Bomberman Game (Medium)

 

The Bomberman Game | HackerRank

Determine the effect of Bomberman's rampage.

www.hackerrank.com

▷ 해결 날짜 : 2022.08.04
▷ 소요 시간 : 1시간 20분
▷ 풀이 과정 :

일단 문제를 보는 순간 풀기 싫게 거부감이 느껴지는 문제이다.

문제의 큰 흐름은 아래와 같다.

 

  1. 초기에 일부 세포에 임의로 폭탄 설치 (0) ( 폭탄이 설치된 상태로 배열이 주어짐 )
  2. 1초 후 침묵  (+1)
  3. 1초 후 폭탄이 없는 모든 곳에 폭탄 설치(+1)
  4. 1초 후 정확히 3초 전에 설치한 폭탄이 폭발 여기서 인접한 상하좌우 같이 터짐(+1)
  5. 계속 3~4 무한 반복

 

그리고 답안은 몇 초 후의 상태를 반환해주면 되는데, 단순히 매 초마다 계산을 하게 되면 시간 초과에 걸릴 것이라는 게 뻔한 문제였다.

그래서 문제의 흐름을 따라가다보면 폭탄이 설치된 그리드의 상태가 반복된다는 것을 알 수 있는데,

이 특징을 알아두고 풀면된다.

 

그렇기 때문에 매 초마다 계산해줄 필요 없이 나 같은 경우에는 4가지 버전의 그리드를 먼저 계산을 해두었다.

 

우선 초기 상태 그리드, 모든 폭탄이 차 있는 상태 그리드, 첫 번째 변화 그리드, 두 번째 변화 그리드 이렇게 4가지 종류이다.

이 4개의 상태를 서로 다른 모습을 가진 그리드만 있으면 쉽게 해결할 수 있는데,

 

우선 초기 상태 그리드는 n이 1초가 나올 수 있기 때문에 필요한 그리드이다.

모든 폭탄이 차 있는 상태 그리드는 2초 단위마다 폭탄을 가득 채우기 때문에 필요한 그리드이며,

그 이후 한번 터지고 난 상태의 첫 번째 변화 그리드, 그 이후 또 터지고 나서의 두 번째 변화 그리드가 필요한 것이다.

 

그걸 미리 계산을 해둔 다음 주어진 n의 값에 따라 필요한 그리드를 반환해주면 이 문제는 해결된다.

 


▷ 구현

function bomberMan(n, grid) {
  // Write your code here
  const ds = [
    [0, 1],
    [1, 0],
    [-1, 0],
    [0, -1],
  ];

  // 나머지 공간 폭탄 처리하기
  const setfillBombsRemainder = (queue, targetGrid) => {
    while (queue.length) {
      const [x, y] = queue.shift();
      for (let i = 0; i < 4; i++) {
        const xPos = x + ds[i][0];
        const yPos = y + ds[i][1];

        if (xPos < 0 || yPos < 0 || xPos >= N || yPos >= M) continue;
        if (targetGrid[xPos][yPos] === "O") targetGrid[xPos][yPos] = ".";
      }
    }
  };
  // n 초후 상태 를 반환
  // 초기 폭탄 상태 grid

  // 3가지 상태가 계속해서 반복
  // 1. 초기에 일부 세포에 임의로 폭탄 설치 (0)
  // 2. 1초 후 침묵  (+1)
  // 3. 1초 후 폭탄이 없는 모든 곳에 폭탄 설치(+1)
  // 4. 1초 후 정확히 3초 전에 설치한 폭탄이 폭발 여기서 인접한 상하좌우 같이 터짐(+1)
  // 5. 계속 3~4 무한 반복
  const [N, M] = [grid.length, grid[0].length];
  const firstGrid = grid.map((v) => v.split(""));
  const fullBombsGrid = grid.map((v) => v.replace(/./g, "O").split(""));
  const queue = [];
  const secondGrid = fullBombsGrid.map((bombs, x) =>
    bombs.map((bomb, y) => {
      if (firstGrid[x][y] === "O") {
        queue.push([x, y]);
        return ".";
      }
      return "O";
    })
  );
  setfillBombsRemainder(queue, secondGrid);
  const thirdGrid = fullBombsGrid.map((bombs, x) =>
    bombs.map((bomb, y) => {
      if (secondGrid[x][y] === "O") {
        queue.push([x, y]);
        return ".";
      }
      return "O";
    })
  );
  setfillBombsRemainder(queue, thirdGrid);

  if (n === 1) return firstGrid.map((v) => v.join(""));
  if (n % 2 === 0) return fullBombsGrid.map((v) => v.join(""));
  else {
    const std = Math.ceil(n / 2);
    return std % 2 === 0
      ? secondGrid.map((v) => v.join(""))
      : thirdGrid.map((v) => v.join(""));
  }
}


▷ 복기 :

뭔가 좀 더 깔끔하게 풀 수 있을 거 같은데, 일단 해결은 됐기 때문에 이 정도로 마무리 하자.

반응형

태그



댓글 0

TOP