[백준] 20057 마법사 상어와 토네이도 (Javascript)

문제

BOJ20057_마법사 상어와 토네이도

코드

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const input = require('fs').readFileSync(filePath).toString().trim().split('\n');
const N = +input[0];
const sandArr = input.slice(1).map((e) => e.split(' ').map(Number));
const now = [N >> 1, N >> 1]; // 현재 좌표 (x,y)
let answer = 0; // 격자 밖으로 나간 모래 양
const left = [
    [-2, 0, 0.02],
    [2, 0, 0.02],
    [-1, 0, 0.07],
    [1, 0, 0.07],
    [-1, -1, 0.1],
    [1, -1, 0.1],
    [-1, 1, 0.01],
    [1, 1, 0.01],
    [0, -2, 0.05],
    [0, -1, 0],
];
const right = left.map(([y, x, ratio]) => [y, -x, ratio]);
const up = left.map(([y, x, ratio]) => [x, y, ratio]);
const down = up.map(([y, x, ratio]) => [-y, x, ratio]);

for (let i = 0; i < N; i++) {
    if (i % 2 === 0) {
        move(i, 0, -1, left);
        move(i, 1, 0, down);
    } else {
        move(i, 0, 1, right);
        move(i, -1, 0, up);
    }
}

console.log(answer);

// 현재 방향으로 토네이도 이동
function move(cnt, y, x, direction) {
    for (let i = 0; i <= cnt; i++) {
        [now[0], now[1]] = [now[0] + y, now[1] + x];
        if (now[0] < 0 || now[1] < 0) break;

        let spreads = 0; // 흩날린 모래의 양
        for (let [dy, dx, ratio] of direction) {
            let [ny, nx] = [now[0] + dy, now[1] + dx];
            let sand = 0;
            if (ratio === 0) {
                // α 위치의 모래 양
                sand = sandArr[now[0]][now[1]] - spreads;
            } else {
                // 비율 위치의 모래 양
                sand = Math.floor(sandArr[now[0]][[now[1]]] * ratio);
            }
            // 퍼진 모래가 범위 안인 경우
            if (0 <= nx && nx < N && 0 <= ny && ny < N) sandArr[ny][nx] += sand;
            // 퍼진 모래가 범위 바깥으로 나갔을 경우
            else answer += sand;
            spreads += sand;
        }
    }
}

풀이

아래와 같은 N * N 크기의 격자판이 있고 중심에서부터 반시계 방향으로 토네이도가 분다.

토네이도가 한 칸 이동할 때마다 각 칸에 있는 모래가 아래와 같은 비율로 흩날린다. (소수점 아래 자리수는 제외)

각 칸의 비율에 따라 흩날리고 남은 모래는 α의 위치로 이동한다.

아래와 같이 모래가 격자의 범위 밖으로 나갈수도 있다.

이럴 경우 범위를 벗어난 모래의 양을 저장해놓는다.

토네이도가 0,0 위치까지 도달하여 소멸하면 범위를 벗어난 모래의 총량을 출력하면 된다.

한번 코드와 함께 살펴보자.

출발점, 이동 방향별 비율 정보 설정

우선 토네이도가 출발하는 중심의 위치부터 잡아준다.

const now = [N >> 1, N >> 1]; // 시작점 좌표

그리고 토네이도가 왼쪽, 오른쪽, 위, 아래로 움직일 때 모래가 흩날리는 비율 정보를 구해놓자.

// 회전 방향에 따른 비율 정보 (y, x, ratio)
const left = [
    [-2, 0, 0.02],
    [2, 0, 0.02],
    [-1, 0, 0.07],
    [1, 0, 0.07],
    [-1, -1, 0.1],
    [1, -1, 0.1],
    [-1, 1, 0.01],
    [1, 1, 0.01],
    [0, -2, 0.05],
    [0, -1, 0],
];
const right = left.map(([y, x, ratio]) => [y, -x, ratio]);
const up = left.map(([y, x, ratio]) => [x, y, ratio]);
const down = up.map(([y, x, ratio]) => [-y, x, ratio]);

토네이도 회전

이제 토네이도가 회전하는 방향에 따라 현재 좌표(now)를 잘 이동시켜주어야 한다.
토네이도의 회전을 보면 규칙이 있다.
왼쪽과 아래로 움직일 때의 이동하는 칸 수가 동일하고, 오른쪽과 위로 움직일 때 이동하는 칸 수가 동일하다.

이를 이용해서 아래와 같이 코드를 작성해줄 수 있다.

for (let i = 0; i < N; i++) {
  // 빨간 부분  
  if (i % 2 === 0) { 
        move(i, 0, -1, left);
        move(i, 1, 0, down);
    } 
  // 파란 부분
  else { 
        move(i, 0, 1, right);
        move(i, -1, 0, up);
    }
}

move 함수 구현

// 현재 방향으로 토네이도 수행
function move(cnt, y, x, direction) {
    for (let i = 0; i <= cnt; i++) {
        [now[0], now[1]] = [now[0] + y, now[1] + x];
        if (now[0] < 0 || now[1] < 0) break;

        let spreads = 0; // 흩날린 모래의 양
      	
        for (let [dy, dx, ratio] of direction) {
            let [ny, nx] = [now[0] + dy, now[1] + dx];
            let sand = 0;
            if (ratio === 0) {
                // α 위치의 모래 양
                sand = sandArr[now[0]][now[1]] - spreads;
            } else {
                // 비율 위치의 모래 양
                sand = Math.floor(sandArr[now[0]][[now[1]]] * ratio);
            }
            // 흩날린 모래가 범위 안인 경우
            if (0 <= nx && nx < N && 0 <= ny && ny < N) sandArr[ny][nx] += sand;
            // 흩날린 모래가 범위 바깥으로 나갔을 경우
            else answer += sand;
            spreads += sand;
        }
    }
}

move 함수의 매개 변수는 각각 아래와 같은 용도로 사용된다

• cnt : 움직일 칸 수
• y, x : 움직일 방향
• direction : 움직이는 방향에 따른 비율 정보

move 함수의 동작은 아래와 같이 나눌수 있다.

1. 현재 좌표 이동
2. 모래 흩날리기
   • α 위치에 저장될 모래의 양 계산하기
   • 비율 위치에 저장될 모래의 양 계산하기
   • 흩날린 모래가 격자 범위 밖으로 나갔을 경우

1. 현재 좌표 이동

현재 좌표를 이동하는 코드는 아래와 같이 작성할 수 있다.

[now[0], now[1]] = [now[0] + y, now[1] + x];
if (now[0] < 0 || now[1] < 0) break;

추가로 좌표를 이동한 뒤, 좌표가 범위를 벗어났다면 반복문을 탈출한다. (cnt === N-1, i === cnt 인 경우)

2. 모래 흩날리기

α 위치에 흩날리고 남은 모래를 저장하기 위해 흩날린 모래의 양을 저장할 spreads 변수를 만들어준다.

let spreads = 0;

for (let [dy, dx, ratio] of direction) {
    let [ny, nx] = [now[0] + dy, now[1] + dx];
    let sand = 0;
    // α 위치에 저장될 모래의 양 계산하기
    if (ratio === 0) {
      sand = sandArr[now[0]][now[1]] - spreads;
    } 
  	// 비율 위치에 저장될 모래의 양 계산하기
  	else {
      sand = Math.floor(sandArr[now[0]][[now[1]]] * ratio);
    }
    // 흩날린 모래가 범위 안에 있다면
    if (0 <= nx && nx < N && 0 <= ny && ny < N) sandArr[ny][nx] += sand;
    // 흩날린 모래가 격자 범위 밖으로 나갔다면
    else answer += sand;
  	// 흩날린 모래의 양 갱신
    spreads += sand;
}

참고

풀이 블로그