[JavaScript] 백준 골드 4 : 20056 - 마법사 상어와 파이어볼

https://www.acmicpc.net/problem/20056

20056번: 마법사 상어와 파이어볼

---

📌 작성한 코드 

// 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);

 

✅ 성공