https://www.acmicpc.net/problem/21610
21610번: 마법사 상어와 비바라기
마법사 상어는 파이어볼, 토네이도, 파이어스톰, 물복사버그 마법을 할 수 있다. 오늘 새로 배운 마법은 비바라기이다. 비바라기를 시전하면 하늘에 비구름을 만들 수 있다. 오늘은 비바라기
www.acmicpc.net
📌 작성한 코드
// 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;
✅ 성공

'알고리즘 > 백준' 카테고리의 다른 글
| [JavaScript] 백준 골드 3 : 18808 - 스티커 붙이기 (0) | 2024.02.16 |
|---|---|
| [JavaScript] 백준 골드 4 : 15683 - 감시 (1) | 2024.02.16 |
| [JavaScript] 백준 골드 5 : 21608 - 상어 초등학교 (1) | 2024.02.13 |
| [JavaScript] 백준 골드 5 : 20055 - 컨베이어 벨트 위의 로봇 (1) | 2024.02.11 |
| [JavaScript] 백준 골드 4 : 16234 - 인구 이동 (1) | 2024.02.11 |