[Node.js] 20056_마법사 상어와 파이어볼

문제

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

 

 

풀이

데이터 구조부터 확인하자.

 

우선 화염구가 들어갈 지도를 배열을 만들어준다.

이때 각 위치에는 화염구의 데이터가 담긴 배열을 담을 수 있는 배열을 추가해준다.

이렇게 한다면 위치별 화염구의 정보를 저장할 수 있다.

 

화염구의 방향은 0부터 7까지 12시 방향부터 10시 방향까지 정해진다.

화염구가 진행할 방향을 dir 변수에 2차원 좌표에서의 백터를 저장해준다.

 

화염구는 한 구역에 여러개 존재할 수 있으며, 2개 이상의 화염구는 서로 합쳐지게된다.

이후 4개의 화염구로 나눠지게 되는데, 이때 화염구의 질량, 속도, 방향이 변하게 된다.

 

질량은 모든 화염구의 질량을 더한 값을 5로 나누고 나머지는 버린 값이 된다.

문제에 ⌊(합쳐진 파이어볼 질량의 합)/5⌋ 부분에서 ⌊ ⌋이 기호는 floor 기호로써 나머지를 버린 값을 의미한다

 

속도는 모든 화염구의 속도를 더한 값에서 화염구의 개수만큼 나누어진 값에서 나머지를 버린 값이다.

 

방향의 경우 질량과 속도를 구하는 방식으로 구하지 않는다. 모든 화염구의 방향이 홀수 혹은 짝수인 경우 [ 0, 2, 4, 6 ], 그 이외의 경우는 [ 1, 3, 5, 7 ] 방향을 갖게된다.

 

가장 어려웠던 부분은 화염구의 이동로직이다.

맵은 링크드 리스트처럼 열과 열, 행과 행이 서로 연결되어있어 맵을 이탈하면 반대방향의 위치로 돌아온다.

또한 화염구는 방향(벡터 값)과 속도(스칼라 값)를 갖기에 방향과 속도를 곱한 값만큼 칸을 이동 한다.

(i + (dir[d][0] * s) % n + n) % n

 

코드

const input = require('fs')
  .readFileSync(process.platform === 'linux' ? '/dev/stdin' : __dirname + '/example.txt')
  .toString().trim().split('\n').map(e => e.split(' ').map(Number));

const [n, m, k] = input.shift().map(Number);
const order = input;
const dir = [[-1, 0], [-1, 1], [0, 1], [1, 1], [1, 0], [1, -1], [0, -1], [-1, -1]];
let map = Array.from({ length: n }, () => Array.from({ length: n }, () => []));
const newDir1 = [0, 2, 4, 6];
const newDir2 = [1, 3, 5, 7];

for (let i = 0; i < m; i++){
  const [x, y, m, s, d] = order[i];
  map[x - 1][y - 1].push([m, s, d]);
}

const mSum = (arr) => {
  let sum = 0;
  arr.forEach(e => {
    sum += e[0];
  })
  return Math.floor(sum / 5);
};

const sSum = (arr) => {
  let sum = 0;
  arr.forEach(e => {
    sum += e[1];
  })
  return Math.floor(sum / arr.length);
};

const newDir = (dirArr) => {
  const allA = dirArr.every(e => e[2] % 2 === 1);
  const allB = dirArr.every(e => e[2] % 2 === 0);
  return allA || allB ? true : false;
};

const move = (existMap) => {
  const newMap = Array.from({ length: n }, () => Array.from({length: n}, () => []));

  for (let i = 0; i < n; i++){
    for (let j = 0; j < n; j++){
      if (existMap[i][j].length > 0) {
        existMap[i][j].forEach(e => {
          const [m, s, d] = e;
          const nx = (i + (dir[d][0] * s) % n + n) % n;
          const ny = (j + (dir[d][1] * s) % n + n) % n;
          
          if (nx >= 0 && nx < n && ny >= 0 && ny < n) {
            newMap[nx][ny].push([m, s, d]);
          }
        })
      }
    }
  }
  
  for (let i = 0; i < n; i++){
    for (let j = 0; j < n; j++){
      if (newMap[i][j].length > 1) {
        const newFireBall = [];
        const newM = mSum(newMap[i][j]);
        const newS = sSum(newMap[i][j]);
        const dir = newDir(newMap[i][j]);

        for (let k = 0; k < 4; k++){
          newFireBall.push([newM, newS, dir ? newDir1[k] : newDir2[k]]);
        }
        newMap[i][j] = newFireBall;
      }
      newMap[i][j] = newMap[i][j].filter(e => e[0] > 0);
    }
  }
  map = newMap;
}
for (let i = 0; i < k; i++){
  move(map);
}

console.log(map.reduce((acc, cur) => {

    return acc + cur.reduce((a, c) => {
      if (c.length === 0) return a;


      return a + c.reduce((ex, ac) => ex + ac[0], 0);
    }, 0);
  
}, 0))