마법사 상어와 파이어볼
📚 문제 설명
N * N 크기의 지도에서 상어가 파이어볼을 발사 했다.
격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
파이어볼은 [ 행, 열, 질량, 속도, 방향 ] 으로 주어지고 방향은 아래와 같다고 한다.
상어가 파이어볼에게 명령을 내리면 아래와 같은 일이 일어난다.
- 모든 파이어볼이 자신의 방향 d로 속력 s칸 만큼 이동한다.
- 이동 후 해당 위치에 2개 이상의 파이어볼이 있다면 파이어볼이 4 방향으로 나누어짐.
- 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같다.
- 질량은 ⌊(합쳐진 파이어볼 질량의 합)/5⌋이다
- 속력은 ⌊(합쳐진 파이어볼 속력의 합)/(합쳐진 파이어볼의 개수)⌋이다.
- 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6이 되고, 그렇지 않으면 1, 3, 5, 7이 된다.
- 질량이 0이 되면 파이어볼은 사라짐.
👨🏻💻 풀이 과정
우선 파이어볼을 저장할 변수를 다음과 같이 2개로 생성했다.
이동 전 파이어볼 : FIREBALL 배열
이동 후 파이어볼 : 3차원 배열 MAP
그리고 이 문제에서 가장 이해가 안되는 부분은 바로 아래 조건일 것이다.
격자의 행과 열은 1번부터 N번까지 번호가 매겨져 있고, 1번 행은 N번과 연결되어 있고, 1번 열은 N번 열과 연결되어 있다.
이말을 예시를 들어 설명하자면 다음과 같다.
- 2 * 2 의 격자에서 파이어볼이
(2,2)위치에 있다고 가정해보자. - 이 때 파이어볼이
d이 3이고s가 1이라면.
| 1 | 2 | |
|---|---|---|
| 1 | ||
| 2 | X |
아래와 같은 격자에서 다음과 같이 움직한다고 생각하면 된다.
따라서 파이어볼의 다음 위치는 (1,1)이 된다.
| 1 | 2 | 1 | 2 | |
|---|---|---|---|---|
| 1 | ||||
| 2 | ||||
| 1 | X | |||
| 2 |
이점을 생각하면서 파이어볼 이동 함수FillMap()을 만들면 다음과 같다.
FIREBALL에서 파이어볼을 하나씩 꺼내서 확인.- 파이어볼 이동.
MAP의 파이어볼 이동 후 위치에 파이어볼 push.
파이어볼 이동 함수
let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const [N, M, K] = input.shift().split(' ').map(Number);
//파이어볼을 인덱스에 맞게 저장.
const FIREBALL = input.map(v => v.split(' ').map(Number).map(v => {
v[0] -= 1;
v[1] -= 1;
return v;
}));
//3차원 배열 생성.
let MAP = Array.from({length: N}, () =>
Array.from({length: N}).map(() => [])
);
// 8방향
const dx = [-1, -1, 0, 1, 1, 1, 0, -1];
const dy = [0, 1, 1, 1, 0, -1, -1, -1];
// 파이어볼 이동.
const FillMap = () => {
while (FIREBALL.length) {
let [X, Y, MASS, SPEED, DIR] = FIREBALL.pop();
// 음수를 대비해 +N 을 진행한 후에 다시 %N
X = (X + (SPEED * dx[DIR]) % N + N) % N;
Y = (Y + (SPEED * dy[DIR]) % N + N) % N;
// MAP에 추가
MAP[X][Y].push([X, Y, MASS, SPEED, DIR]);
}
};이제 이동 후 파이어볼이 모두 MAP 배열에 저장이 되었기 때문에 MAP 배열을 전부 확인.
- 파이어볼이 2개 이상이면
- 파이어볼을 합치고 4개로 나눔.
FIREBALL배열에 push.
- 파이어볼이 1개라면
- 바로
FIREBALL배열에 push.
- 바로
MAP 확인 후 파이어볼 추가
// 파이어볼 4분할시 방향
const goX = [1, 3, 5, 7];
const goPlus = [0, 2, 4, 6];
// 파이어볼 이동 후 함수.
const Divide = () => {
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
// 만약 같은 곳에 파이어볼이 2개 이상일 경우
if (MAP[i][j].length > 1) {
let [SumMass, SumSpeed, cntEven, cnt] = [0, 0, 0, MAP[i][j].length];
while (MAP[i][j].length) {
// 파이어볼의 질량과 속도를 모두 더함.
const PopItem = MAP[i][j].pop();
SumMass += PopItem[2];
SumSpeed += PopItem[3];
// 파이어볼의 방향이 모두 짝수인지 모두 홀수인지 확인.
cntEven = PopItem[4] % 2 === 0 ? cntEven + 1 : cntEven;
}
// 4분할 방향 결정.
let Splash = cntEven === cnt || cntEven === 0 ? goPlus : goX;
// 만약 질량이 0이 아니면.
if (Math.floor(SumMass / 5)) {
for (const direction of Splash) {
// 파이어볼 배열에 저장.
FIREBALL.push([i, j, Math.floor(SumMass / 5), Math.floor(SumSpeed / cnt), direction]);
}
}
}
// 만약 해당 위치에 파이어볼이 1개라면.
if (MAP[i][j].length === 1) {
// MAP에서 꺼낸 후 파이어볼 배열에 추가.
const PopItem = MAP[i][j].pop();
FIREBALL.push(PopItem);
}
}
}
};최종적으로 K번 동안 FillMap()와 Divide()함수 실행,
reduce() 를 이용해 FIREBALL 배열에서 질량을 모두 더한 값을 리턴해주면 된다.
전체 풀이
let fs = require("fs");
let input = fs.readFileSync("./input.text").toString().trim().split('\n');
// let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
const [N, M, K] = input.shift().split(' ').map(Number);
//파이어볼을 인덱스에 맞게 저장.
const FIREBALL = input.map(v => v.split(' ').map(Number).map(v => {
v[0] -= 1;
v[1] -= 1;
return v;
}));
//3차원 배열 생성.
let MAP = Array.from({length: N}, () =>
Array.from({length: N}).map(() => [])
);
// 8방향
const dx = [-1, -1, 0, 1, 1, 1, 0, -1];
const dy = [0, 1, 1, 1, 0, -1, -1, -1];
// 파이어볼 4분할시 방향
const goX = [1, 3, 5, 7];
const goPlus = [0, 2, 4, 6];
// 파이어볼 이동.
const FillMap = () => {
while (FIREBALL.length) {
let [X, Y, MASS, SPEED, DIR] = FIREBALL.pop();
// 음수를 대비해 +N 을 진행한 후에 다시 %N
X = (X + (SPEED * dx[DIR]) % N + N) % N;
Y = (Y + (SPEED * dy[DIR]) % N + N) % N;
// MAP에 추가
MAP[X][Y].push([X, Y, MASS, SPEED, DIR]);
}
};
// 파이어볼 이동 후 함수.
const Divide = () => {
for (let i = 0; i < N; i++) {
for (let j = 0; j < N; j++) {
// 만약 같은 곳에 파이어볼이 2개 이상일 경우
if (MAP[i][j].length > 1) {
let [SumMass, SumSpeed, cntEven, cnt] = [0, 0, 0, MAP[i][j].length];
while (MAP[i][j].length) {
// 파이어볼의 질량과 속도를 모두 더함.
const PopItem = MAP[i][j].pop();
SumMass += PopItem[2];
SumSpeed += PopItem[3];
// 파이어볼의 방향이 모두 짝수인지 모두 홀수인지 확인.
cntEven = PopItem[4] % 2 === 0 ? cntEven + 1 : cntEven;
}
// 4분할 방향 결정.
let Splash = cntEven === cnt || cntEven === 0 ? goPlus : goX;
// 만약 질량이 0이 아니면.
if (Math.floor(SumMass / 5)) {
for (const direction of Splash) {
// 파이어볼 배열에 저장.
FIREBALL.push([i, j, Math.floor(SumMass / 5), Math.floor(SumSpeed / cnt), direction]);
}
}
}
// 만약 해당 위치에 파이어볼이 1개라면.
if (MAP[i][j].length === 1) {
// MAP에서 꺼낸 후 파이어볼 배열에 추가.
const PopItem = MAP[i][j].pop();
FIREBALL.push(PopItem);
}
}
}
};
// 메인 함수.
const solution = () => {
// K번 반복
for (let i = 0; i < K; i++) {
FillMap();
Divide();
}
// reduce 함수를 이용해 질량을 더해줌.
return FIREBALL.reduce((acc, cur) => {
return acc + cur[2];
}, 0);
};
console.log(solution());🧐 후기
이 문제에서 가장 헤맸던 부분은 바로 파이어볼을 합치는 부분이었다.
3차원 배열로 파이어볼을 저장하기 싫어서 파이어볼 배열 1개로 해결하려 했는데 도저히 방법이 떠오르지 않아 다른 사람들은 파이어볼을 합치기 위해 어떻게 하나 확인했는데 3차원 배열로 따로 저장한 후에 그곳에서 전부 합치는 방법을 쓰는 것을 보고 그냥 3차원 배열을 활용하여 풀었다.
JavaScript를 사용하는 모두를 위해...