▷ 문제 : The Bomberman Game (Medium)
The Bomberman Game | HackerRank
Determine the effect of Bomberman's rampage.
www.hackerrank.com
▷ 해결 날짜 : 2022.08.04
▷ 소요 시간 : 1시간 20분
▷ 풀이 과정 :
일단 문제를 보는 순간 풀기 싫게 거부감이 느껴지는 문제이다.
문제의 큰 흐름은 아래와 같다.
- 초기에 일부 세포에 임의로 폭탄 설치 (0) ( 폭탄이 설치된 상태로 배열이 주어짐 )
- 1초 후 침묵 (+1)
- 1초 후 폭탄이 없는 모든 곳에 폭탄 설치(+1)
- 1초 후 정확히 3초 전에 설치한 폭탄이 폭발 여기서 인접한 상하좌우 같이 터짐(+1)
- 계속 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(""));
}
}
▷ 복기 :
뭔가 좀 더 깔끔하게 풀 수 있을 거 같은데, 일단 해결은 됐기 때문에 이 정도로 마무리 하자.
댓글