[JavaScript] 백준 골드 5 : 21610 - 마법사 상어와 비바라기

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

21610번: 마법사 상어와 비바라기

---

📌 작성한 코드 

// 21610
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] = input.shift().split(" ").map(Number);
const board = [];
for (let i = 0; i < N; i++) {
    board.push(input.shift().split(" ").map(Number));
}
const move = input.map((str) => str.split(" ").map(Number));

const dx = [0, -1, -1, -1, 0, 1, 1, 1];
const dy = [-1, -1, 0, 1, 1, 1, 0, -1];

const wx = [-1, -1, 1, 1];
const wy = [1, -1, -1, 1];

// 1. 구름 생성
let cloud = [
    [N - 1, 0],
    [N - 1, 1],
    [N - 2, 0],
    [N - 2, 1],
];

for (let i = 0; i < M; i++) {
    let [d, s] = move[i];
    // 2. 구름 이동하기
    const newCloud = [];
    const visited = Array.from({ length: N }, () => new Array(N).fill(false));
    cloud.forEach(([x, y]) => {
        const nx = (x + dx[d - 1] * s + N * 100) % N;
        const ny = (y + dy[d - 1] * s + N * 100) % N;

        visited[nx][ny] = true;
        newCloud.push([nx, ny]);
        // 3. 물의 양 증가
        board[nx][ny] += 1;
    });

    // 4. 물 복사 버그
    newCloud.forEach(([x, y]) => {
        let plusWater = 0;
        for (let i = 0; i < 4; i++) {
            const nx = x + wx[i];
            const ny = y + wy[i];

            if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
            if (board[nx][ny] > 0) plusWater++;
        }

        board[x][y] += plusWater;
    });

    // 5. 새로운 구름 생성
    const tempCloud = [];
    for (let x = 0; x < N; x++) {
        for (let y = 0; y < N; y++) {
            if (board[x][y] >= 2 && !visited[x][y]) {
                board[x][y] -= 2;
                tempCloud.push([x, y]);
            }
        }
    }
    cloud = tempCloud;
}

let answer = 0;
for (let i = 0; i < N; i++) {
    for (let j = 0; j < N; j++) {
        answer += board[i][j];
    }
}

console.log(answer);

📌 풀이 

구름을 이동하고, 물을 복사하는 단계를 반복하면서 최종적으로 물이 몇 개(바구니에 담긴 물의 총량)인지 구하는 `구현` 문제이다.

문제에서 단계를 자세히 설명하고 있으니, 해당 단계를 잘 구현하는 것에 집중하면 되는 문제이다.

(1) 구름을 생성한다. (단 맨 처음에 한 번 만 (N, 1), (N, 2), (N-1, 1), (N-1, 2) 좌표에 생성해야 한다.)
(2) 구름을 이동시킨다. (입력받은 방향`d`으로 `s`칸 만큼 이동시킨다. 모든 좌표가 연결되어있으니 범위 벗어나도 계속 이동 시킨다. 0<->N)
(3) 이동한 위치에 비를 내린다.
(4) 물 복사 버그를 사용하여 대각선에 물이 위치한 수 만큼 물을 복사시킨다.(단, 대각선 확인은 범위 벗어난 좌표를 확인하지 않는다.)
(5) (2)번에 위치한 곳을 제외하고 물이 있는 곳에 구름을 생성한다.

특히 주의해야 하는 부분은 좌표의 연속성 부분이다

- (2) 단계에서는 좌표가 이어져 있기 때문에 이동 위치를 N으로 나눠서 다시 N*N 사이의 좌표에 들어올 수 있게 연산해줘야 한다.

- (4) 단계에서는 범위를 벗어난 좌표를 확인하지 않는다. 

 

(1) 구름을 생성한다.

- 초기값으로 주어진 위치를 배열에 저장한다.

// 1. 구름 생성
let cloud = [
    [N - 1, 0],
    [N - 1, 1],
    [N - 2, 0],
    [N - 2, 1],
];

(2) 구름을 이동한다.

- d 방향으로 s만큼 이동한다. 

- d 방향은 숫자로 주어지는데 <- 방향이 기준이 되어 1이 되고, 나머지 방향은 시계 방향으로 2,3,4,... 증가하는 방식으로 숫자가 주어진다. 

- 사전에 화살표 방향에 대한 좌표를 선언해두고, d를 통해 접근해서 해당 방향으로 이동할 수 있게 해주었다.

- s번 갈 것이므로 * s를 해주고, -로 이동하는 경우에는 값이 음수가 될 수 있기 때문에 N을 곱해서 0~N-1 사이의 숫자가 될 수 있도록 만들어준다. 

const dx = [0, -1, -1, -1, 0, 1, 1, 1];
const dy = [-1, -1, 0, 1, 1, 1, 0, -1];

// ...

for (let i = 0; i < M; i++) {
    let [d, s] = move[i];
    // 2. 구름 이동하기
    const newCloud = [];
    const visited = Array.from({ length: N }, () => new Array(N).fill(false));
    cloud.forEach(([x, y]) => {
        const nx = (x + dx[d - 1] * s + N * 100) % N;
        const ny = (y + dy[d - 1] * s + N * 100) % N;

        visited[nx][ny] = true;
        newCloud.push([nx, ny]);
        // 3. 물의 양 증가
        board[nx][ny] += 1;
    });

(3) 비를 내린다.

- 이동한 좌표가 새로운 구름의 위치이니까, 해당 좌표를 저장해준다. (newCloud와 visited에 모두 저장해준다.) 

- 그리고 새로운 구름 좌표에 비를 내려준다. 

 

(4) 물 복사 버그를 사용한다.

- 새로운 구름이 존재하는 곳의 대각선 네 방향을 확인하고 , 물이 존재하는 대각선 위치의 수를 세서 해당 수만큼 물을 복사해준다(더해준다).

- 범위를 벗어나면 계산하지 않으니까 범위를 꼭 확인해줘야 한다. 

const wx = [-1, -1, 1, 1];
const wy = [1, -1, -1, 1];

// ...

newCloud.forEach(([x, y]) => {
    let plusWater = 0;
    for (let i = 0; i < 4; i++) {
        const nx = x + wx[i];
        const ny = y + wy[i];

        if (nx < 0 || nx >= N || ny < 0 || ny >= N) continue;
        if (board[nx][ny] > 0) plusWater++;
    }

    board[x][y] += plusWater;
});

 

(5) 새로운 구름을 생성한다.

- 이동한 구름이 위치한 곳이 아니면서, 물이 2개 이상 있는 곳에서 구름이 생성가능하다. 

- 이때 구름이 특정 좌표에 있는지 확인하기 위해서 `visited` 배열을 사용한다. (앞선 코드에서 `newCloud` 배열에 구름 좌표를 저장해놓고도 `visited`에 또 저장한 이유이다. newCloud를 통해 확인하기는 복잡하기 때문이다.)

const tempCloud = [];
    for (let x = 0; x < N; x++) {
        for (let y = 0; y < N; y++) {
            if (board[x][y] >= 2 && !visited[x][y]) {
                board[x][y] -= 2;
                tempCloud.push([x, y]);
            }
        }
    }
    cloud = tempCloud;

 

✅ 성공