마법사 상어와 파이어볼

문제

백준 20056번 - 마법사 상어와 파이어볼

언어

JavaScript

순서도

N x N 크기의 격자에 파이어볼 정보 넣기
k 번 만큼, 파이어볼을 이동시키고 합치기
- 각 파이어볼을 속도와 방향에 맞게 적절히 이동시키기
- 각 격자에서 파이어볼이 2 개 이상이라면, 모두 합친 후 질량과 속도와 방향에 대해서 적절하게 4 개의 파이어볼로 나누기
격자를 다 순회하며, 파이어볼의 질량 구하기

문제 풀이 step 1

본 문제는 시뮬레이션 형식의 문제로, 문제에서 주어진 조건대로 로직을 짜는 문제입니다.
마법사 상어가 크기가 N x N 인 격자에 파이어볼 M 개를 발사했습니다.
가장 처음에 파이어볼은 각자 위치에서 이동을 대기하고 있습니다. i 번 파이어볼의 위치는 (ri, ci), 질량은 mi 이고, 방향은 di, 속력은 si 입니다.
격자의 행은 열과 1번 부터 N 번까지 번호가 매겨져 있고, 1 번 행은 N 번 행과 연결되어 있고, 1 번 열은 N 번 열과 연결되어 있습니다.
- 이 말은 곧, 파이어볼이 격자 내부에서 밖으로 나갈 수 없음을 의미합니다.
파이어볼의 방향은 자신이 있는 위치에서 총 8 개의 방향으로 이동할 수 있습니다.
마법사 상어가 모든 파이어볼에게 이동을 명령하면 다음과 같은 일들이 일어납니다.
1. 모든 파이어볼이 자신의 방향 di 로 속력 si 칸 만큼 이동
  - 이동 중 같은 칸에 여러 개의 파이어볼이 존재 가능
2. 이동이 모두 끝난 뒤, 2 개 이상의 파이어볼이 있는 칸에서는 다음과 같은 일이 일어남
  - 같은 칸에 있는 파이어볼은 모두 하나로 합쳐짐
  - 파이어볼은 4 개의 파이어볼로 나누어짐
  - 나누어진 파이어볼의 질량, 속력, 방향은 다음과 같아짐
    - 질량은 (합쳐진 파이어볼 질량의 합) / 5 에서 소수점 이하의 값을 버린 값
    - 속력은 (합쳐진 파이어볼 속력의 합) / (합쳐진 파이어볼의 개수) 에서 소수점 이하의 값을 버린 값
    - 합쳐지는 파이어볼의 방향이 모두 홀수이거나 모두 짝수이면, 방향은 0, 2, 4, 6 이 되고, 그렇지 않으면 1, 3, 5, 7 이 됨
  - 질량이 0 인 파이어볼은 소멸되어 없어짐
마법사 상어가 파이어볼에게 k 번 이동을 명령한 후에 남아있는 파이어볼의 질량의 합을 구하는 문제입니다.

문제 풀이 step 2

위의 정보를 기반해서 N x N 크기의 격자에 파이어볼의 정보를 저장 후 적절히 이동 후에 남아있는 파이어볼의 질량의 합을 구하는 문제입니다.
우선, N x N 크기의 격자를 만들고, 입력 정보를 넣어줍니다.
- 각 격자에는 [질량, 속도, 방향] 형태의 값이 들어갑니다.
k 번 만큼 파이어볼을 이동시키고 합치는 과정을 수행합니다.
- 이동하는 과정
  - 우선, 파이어볼의 이동 방향 8 가지를 저장합니다.
  - 각 파이어볼에 대해서 자신의 속도만큼 이동을 시켜서 좌표 값을 변환시킵니다.
  - 이 때, 1 번 행은 N 번 행과 연결되어 있고, 1 번 열은 N 번 열과 연결되어 있으므로, 좌표값이 음수가 되거나 N 을 넘어가면 적절하게 조치를 해줍니다.
- 합치는 과정
  - 만약 칸에 파이어볼이 1 개 이하로 있다면 넘어가고, 2 개 이상일 때만 합칩니다.
  - 칸에 있는 파이어볼의 모든 질량과 모든 속도를 합칩니다. 그리고 합친 질량은 5 로 나누고, 합친 속도는 파이어볼의 개수로 나눈 뒤 소수점 이하의 값을 제거합니다.
  - 만약 질량이 0 이라면, 칸에 있는 모든 파이어볼은 제거하고, 0 이 아니라면, 각 파이어볼의 방향 정보에 따라서 적절하게 격자에 4 개의 파이어볼을 넣어줍니다.
위 과정을 수행한 후에 격자 안에 남아있는 파이어볼들의 질량의 합을 구해서 출력하면 정답입니다.
추가 설명은 주석으로 작성하겠습니다.

후기

꼭 다시 풀어볼 문제입니다.
시간초과가 발생해서 많은 시행착오를 겪었습니다.
파이어볼의 이동을 구현할 때 s 칸 만큼 이동하는 것을 1 씩 증가하는 반복문으로 구현했더니 소요시간이 상당히 크게 나왔습니다.
이런 경우, 곱셈으로 구하는 것이 훨씬 빠른 구현 방법이라는 것을 깨달을 수 있었습니다.
또한 음수의 경우에도 MOD 연산 (%) 이 양수와 크게 다르지 않게 동작한다는 것도 깨달을 수 있었습니다.

소스 코드

const input = require("fs")
	.readFileSync("/dev/stdin")
	.toString()
	.trim()
	.split("\n");

const dir = [
	[-1, 0],
	[-1, 1],
	[0, 1],
	[1, 1],
	[1, 0],
	[1, -1],
	[0, -1],
	[-1, -1],
];

// 파이어볼의 이동을 구현하는 함수
const moveFireballs = (n, grid) => {
	// 새로운 격자 생성
	const nGrid = Array.from({length: n}, () =>
		Array.from({length: n}, () => [])
	);

	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j].length === 0) continue;

			// 칸 안에 있는 파이어볼들에 대해서
			while (grid[i][j].length) {
				const [m, s, d] = grid[i][j].pop();

				// 파이어볼의 속도만큼 칸 이동 후 n 으로 나머지 연산 수행
				let [r, c] = [(i + dir[d][0] * s) % n, (j + dir[d][1] * s) % n];
				// 좌표가 음수일 때 예외 처리
				if (r < 0) r += n;
				if (c < 0) c += n;

				nGrid[r][c].push([m, s, d]);
			}
		}
	}

	// 새로운 격자 return
	return nGrid;
};

const combineFireballs = (n, grid) => {
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			const fireballCnt = grid[i][j].length;

			// 파이어볼이 1 개 이하인 경우 넘김
			if (fireballCnt < 2) continue;

			let [m, s] = [0, 0];
			let [odd, even] = [0, 0];
			while (grid[i][j].length) {
				[fm, fs, fd] = grid[i][j].pop();

				// 파이어볼들의 질량의 총합과 속력의 총합 구하기
				m += fm;
				s += fs;

				// 파이어볼들의 이동 방향이 짝수인지 홀수인지 조사
				if (fd % 2 === 0) even += 1;
				else odd += 1;
			}

			// 파이어볼들의 질량과 속력 구하기
			const [divM, divS] = [Math.floor(m / 5), Math.floor(s / fireballCnt)];

			// 질량이 0 이면, 넘김
			if (divM === 0) continue;

			// 파이어볼들의 이동 방향에 따라서 적절히 방향 정해주기
			let k;
			if (odd === fireballCnt || even === fireballCnt) {
				k = 0;
			} else {
				k = 1;
			}

			while (k < 8) {
				grid[i][j].push([divM, divS, k]);

				k += 2;
			}
		}
	}
};

// n: 격자의 크기, m: 파이어볼의 개수, k: 명령의 개수,
const solution = (input) => {
	let [n, m, k] = input[0].split(" ").map(Number);

	let grid = Array.from({length: n}, () => Array.from({length: n}, () => []));
	for (let i = 1; i < m + 1; i++) {
		const [r, c, m, s, d] = input[i].split(" ").map(Number);

		grid[r - 1][c - 1].push([m, s, d]);
	}

	// k 번 만큼, 파이어볼의 이동과 합치기 진행
	while (k-- > 0) {
		grid = moveFireballs(n, grid);
		combineFireballs(n, grid);
	}

	// 남아있는 파이어볼들의 질량의 총합 구하기
	let sum = 0;
	for (let i = 0; i < n; i++) {
		for (let j = 0; j < n; j++) {
			if (grid[i][j].length === 0) continue;

			while (grid[i][j].length) {
				[m, s, d] = grid[i][j].pop();

				sum += m;
			}
		}
	}

	return sum;
};

console.log(solution(input));