https://www.acmicpc.net/problem/20056
20056번: 마법사 상어와 파이어볼
첫째 줄에 N, M, K가 주어진다. 둘째 줄부터 M개의 줄에 파이어볼의 정보가 한 줄에 하나씩 주어진다. 파이어볼의 정보는 다섯 정수 ri, ci, mi, si, di로 이루어져 있다. 서로 다른 두 파이어볼의 위치
www.acmicpc.net
📌 작성한 코드
// 14499
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M, K] = input.shift().split(" ").map(Number);
let fireball = input.map((str) => str.split(" ").map(Number));
const dx = [-1, -1, 0, 1, 1, 1, 0, -1];
const dy = [0, 1, 1, 1, 0, -1, -1, -1];
const board = Array.from({ length: N }, () => Array.from({ length: N }, () => new Array(0)));
fireball.forEach(([r, c, m, s, d]) => {
board[r - 1][c - 1].push([m, s, d]);
});
for (let t = 0; t < K; t++) {
const tempFire = [];
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (board[i][j].length) {
board[i][j].forEach((v) => {
const [m, s, d] = v;
const nx = (i + dx[d] * s + N * 100000) % N;
const ny = (j + dy[d] * s + N * 100000) % N;
tempFire.push([nx, ny, m, s, d]);
});
}
board[i][j] = [];
}
}
tempFire.forEach(([x, y, m, s, d]) => {
board[x][y].push([m, s, d]);
});
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (board[i][j].length > 1) {
const totalM = Math.floor(board[i][j].reduce((sum, cur) => sum + cur[0], 0) / 5);
const totalS = Math.floor(board[i][j].reduce((sum, cur) => sum + cur[1], 0) / board[i][j].length);
let [isEven, isOdd] = [true, true];
board[i][j].forEach(([m, s, d]) => {
if (d % 2 === 0) isOdd = false;
else isEven = false;
});
if (totalM === 0) {
board[i][j] = [];
continue;
}
let dirList = isEven || isOdd ? [0, 2, 4, 6] : [1, 3, 5, 7];
const temp = [];
dirList.forEach((d) => {
temp.push([totalM, totalS, d]);
});
board[i][j] = temp;
}
}
}
}
let sum = 0;
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (board[i][j].length) {
board[i][j].forEach((v) => {
const [m, s, d] = v;
sum += m;
});
}
}
}
console.log(sum);
📌 설명
파이어볼을 이동시키고, 합체하고, 다시 분리시키면서 최종적으로 남은 파이어볼의 질량 총합을 구하는 문제이다. 긴 설명과 복잡한 파이어볼 이동 방식을 보면 알겠지만 하나하나 직접 구현해야하는 시뮬레이션 문제이다.
파이어볼 이동 순서
(1) 모든 파이어볼이 자신이 가진 속도와 방향으로 이동한다.
- 이때 한 칸에 여러개의 파이어볼이 존재할 수 있다. (매우 주의해야 하는 부분! 2번에는 여러개의 파이어볼일 때 합체하지만 여기서는 그냥 둔다)
(2) 이동이 끝난 뒤 2개 이상의 파이어볼이 있는 곳에서는 합체 -> 분리가 일어난다.
- 이 때 분리하게 되면 같은 칸에 여러개의 파이어볼이 존재하게 된다. 그래서 (1)번 단계에서 한 칸에 여러개의 파이어볼이 존재할 수 있는 것이다.
(1) 초기 세팅하기
- 문제에서 주어진 방향에 따라서 dx,dy를 정의한다. (dx[0]을 하면 0번 칸으로 이동할 수 있게하는 dx 값을 정의)
- 파이어볼이 위치할 N * N board를 정의한다. 여러 개의 파이어볼을 저장하기 위해 각 좌표에 배열을 선언해서 3차원 배열을 생성한다.
- 입력 받은 파이어볼을 board에 저장한다. 좌표를 0~N-1까지 사용하기 위해서 좌표에 저장할 때 r-1,c-1에 저장해주었다.
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");
const [N, M, K] = input.shift().split(" ").map(Number);
let fireball = input.map((str) => str.split(" ").map(Number));
const dx = [-1, -1, 0, 1, 1, 1, 0, -1];
const dy = [0, 1, 1, 1, 0, -1, -1, -1];
const board = Array.from({ length: N }, () => Array.from({ length: N }, () => new Array(0)));
fireball.forEach(([r, c, m, s, d]) => {
board[r - 1][c - 1].push([m, s, d]);
});
(2) 파이어볼 이동하기
- 2중 포문을 돌면서 각 좌표에 파이어볼이 있는지 확인하고, 파이어볼의 개수만큼 반복을 돌며 해당 파이어볼을 이동시킨다.
- 주의해야 할 점은 0번 열과 N-1번 열이 연결되어 있고, 0번 행과 N-1번 행이 연결되어 있다는 점이다. 따라서 N-1 다음 좌표는 다시 0이 된다. 따라서 새로 이동하게 될 nx를 구할 때는 현재 위치에서 방향, 속력을 사용해서 이동한 후에 다시 0~N-1 사이 범위에 들어오도록 조정을 해주어야 한다.
- d의 방향으로 s만큼 이동할 것이므로 nx = x + dx[d] * s 가 된다. 이렇게 한 후에 범위 안으로 들어가게 하기 위해서 다시 N으로 나눈 나머지를 nx로 사용할 것이다. 예를 들어 N이 4라고 했을 때 좌표의 끝은 3이다. 각 열과 행의 끝은 연결되어 있으니 4가 나온 경우 다시 0이 되어야 한다. 그렇게 만들기 위해서는 4로 나눠주면 된다.
- 그런데 여기서 주의해야 할 부분은 dx[d]가 음수를 가진 경우이다. 좌표는 모두 양수이므로 x가 이동하다가 음수인 좌표로 넘어가게 되면, N으로 나눈다고 해서 원하는 좌표로 만들 수 없다. 그래서 양수로 만들어주기 위해서 N의 배수를 더해준다. 충분히 큰 수의 N의 배수를 더해주지 않으면 음수가 나올 수 있다. 그래서 나는 N * 100000을 더해주었다.
- 이동한 좌표를 임시 배열에 저장해둔다. 바로 board에 업데이트 하게되면, 이중 포문을 도는 동안 새로 이동한 파이어볼을 또 이동시키는 문제가 발생할 수 있기 때문이다.
- 이동 후에는 원래 존재하던 좌표에서 해당 파이어볼을 삭제해준다.
const tempFire = [];
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (board[i][j].length) {
board[i][j].forEach((v) => {
const [m, s, d] = v;
const nx = (i + dx[d] * s + N * 100000) % N;
const ny = (j + dy[d] * s + N * 100000) % N;
tempFire.push([nx, ny, m, s, d]); // 임시 배열에 저장
});
}
board[i][j] = []; // 파이어볼 삭제
}
}
tempFire.forEach(([x, y, m, s, d]) => { // 모든 이동 후에 파이어볼 원본 배열에 저장하기
board[x][y].push([m, s, d]);
});
(3) 파이어볼 합체 / 분리하기
- 파이어볼 이동 후에, 다시 반복문을 돌면서 한 좌표에 여러개의 파이어볼이 있는지 확인한다.
- 여러개의 파이어볼이 존재하면, 해당 파이어볼을 합치고 다시 4개로 나눈다.
- 나눠진 파이어볼은 원래 파이어볼이 존재하던 위치에 다시 저장한다.

for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (board[i][j].length > 1) {
// 나눠질 파이어볼의 질량과 속력 구하기
const totalM = Math.floor(board[i][j].reduce((sum, cur) => sum + cur[0], 0) / 5);
const totalS = Math.floor(board[i][j].reduce((sum, cur) => sum + cur[1], 0) / board[i][j].length);
let [isEven, isOdd] = [true, true];
board[i][j].forEach(([m, s, d]) => { // 파이어볼들의 방향을 확인한다.
if (d % 2 === 0) isOdd = false;
else isEven = false;
});
if (totalM === 0) { // 새로운 파이어볼의 질량이 0이면 소멸시킨다.
board[i][j] = [];
continue;
}
let dirList = isEven || isOdd ? [0, 2, 4, 6] : [1, 3, 5, 7]; // 파이어볼의 홀/짝 OR 혼합 기준에 따라 방향을 정한다.
const temp = [];
dirList.forEach((d) => {
temp.push([totalM, totalS, d]); // 새로운 질량, 속도, 방향을 저장한다.
});
board[i][j] = temp; // 원래 파이어볼이 존재하던 좌표에 새로운 파이어볼을 넣는다.
}
}
}
(4) 질량의 총 합 구하기
- 반복문을 돌며 각 파이어볼의 총 질량을 구한다.
let sum = 0;
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
if (board[i][j].length) {
board[i][j].forEach((v) => {
const [m, s, d] = v;
sum += m;
});
}
}
}
console.log(sum);
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript/구현] 백준 골드 3 : 14890 - 경사로 (1) | 2024.03.06 |
|---|---|
| [JavaScript/DP] 백준 실버 1 : 1890 - 점프 (3) | 2024.03.04 |
| [JavaScript] 백준 골드 4 : 14499 - 주사위 굴리기 (0) | 2024.03.01 |
| [JavaScript/DP] 백준 골드 5 : 2240 - 자두나무 (0) | 2024.02.29 |
| [JavaScript/Greedy] 백준 골드 4 : 1744 - 수 묶기 (0) | 2024.02.29 |