BOJ 23291 - 어항 정리 (Javascript)

문제 링크

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

23291번: 어항 정리

 

풀이

개요

문제가 복잡합니다. 과정별로 반복되는 행동을 정리해서 구현합시다.

기본적으로 어항들을 이차원 배열로 관리합니다. 함수형 패러다임을 이용하면 과정별로 함수를 만들어 잘 조립해주기만 하면 됩니다.

 

1. 물고기의 수가 가장 적은 어항에 물고기를 한 마리 넣는다. 이를 addFish() 함수에서 구현합니다.

2. 어항을 규칙에 따라 쌓는다. 설명이 복잡하지만 어항을 돌돌 말아버린다고 생각하면 됩니다. 이를 roll() 함수에서 구현합니다. rollOnce()라는 한 번 말아주는 함수를 구현하고, 조건을 만족하는 동안 계속해서 호출하는 방식으로 구현했습니다.

3. 물고기 수를 조절한다. distribute() 함수에서 구현합니다.

4. 어항을 바닥에 일렬로 놓는다. flat() 함수에서 구현합니다.

5. 공중 부양을 하는데, 사실 반으로 접는 연산이라고 생각하면 됩니다. fold() 함수에서 구현합니다.

6. 한번 더 fold 합니다.

7. distribute 합니다.

8. flat 합니다.

 

이 과정을 조건을 만족할 때까지 반복하면 됩니다.

 

유틸 함수 설명

pipe

const pipe = (...fs) => fs.reduce((g, f) => f(g));

함수의 합성을 알아보기 쉽게 작성할 수 있도록 도와주는 함수입니다.

f4(f3(f2(f1(x))))

pipe를 이용하면 위 코드를 다음과 같이 작성할 수 있습니다.

pipe(
  x,
  f1,
  f2,
  f3,
  f4,
)

 

transpose, reverse, rotate

const transpose = arr => arr[0].map((_, i) => arr.map(row => row[i]));
const reverseUD = arr => [...arr].reverse();
const reverseLR = arr => arr.map(row => row.reverse());
const rotateCW = arr => reverseLR(transpose(arr));

함수형으로 깔끔하게 2차원 배열을 회전시킬 수 있습니다.

놀랍게도 전치 행렬을 구한 뒤 위아래로 뒤집으면 반시계 방향 회전, 좌우로 뒤집으면 시계 방향 회전을 하게 됩니다.

 

sum

const sum = arr => arr.reduce((a, b) => a + b, 0);

배열을 받아 합을 구해주는 함수입니다.

 

max, minBowlValue

const maxBowlValue = bowls => Math.max(...bowls.flat());
const minBowlValue = bowls => Math.min(...bowls.flat());

단순한 2차원 max, min입니다.

 

zip

const zip = (arr, concatable) => {
  const getConcatableRow = index =>
    index < concatable.length ? concatable[index] : [];
  return arr.map((row, i) => [...row, ...getConcatableRow(i)]);
};

두 배열을 엮어주는 함수입니다. 사실 보편적인 zip 함수는 다음처럼 동작합니다.

const a = [1, 2, 3], b = [4, 5, 6];

zip(a, b) // [[1, 4], [2, 5], [3, 6]]

제가 구현한 zip은 2차원 배열을 대상으로 다음처럼 동작합니다.

const a = [[1, 2, 3], [4, 5, 6], [7, 8]]
const b = [[10, 11], [12, 13, 14], [15, 16, 17]]

zip(a, b)
// [ [ 1, 2, 3, 10, 11 ], [ 4, 5, 6, 12, 13, 14 ], [ 7, 8, 15, 16, 17 ] ]

정답 코드

// @BOJ ------------------------------------------
const fs = require('fs');
const stdin = fs.readFileSync('/dev/stdin').toString().split('\n');
const input = (() => {
  let line = 0;
  const input = () => stdin[line++];
  input.num = () => input().split(' ').map(Number);
  input.rows = l => Array(l).fill().map(input);
  input.rows.num = l => Array(l).fill().map(input.num);
  return input;
})();

// Solution -----------------------------------
const pipe = (...fs) => fs.reduce((g, f) => f(g));
const transpose = arr => arr[0].map((_, i) => arr.map(row => row[i]));
const reverseUD = arr => [...arr].reverse();
const reverseLR = arr => arr.map(row => row.reverse());
const rotateCW = arr => reverseLR(transpose(arr));
const sum = arr => arr.reduce((a, b) => a + b, 0);
const maxBowlValue = bowls => Math.max(...bowls.flat());
const minBowlValue = bowls => Math.min(...bowls.flat());

const zip = (arr, concatable) => {
  const getConcatableRow = index =>
    index < concatable.length ? concatable[index] : [];
  return arr.map((row, i) => [...row, ...getConcatableRow(i)]);
};

const addFish = bowls => {
  const min = minBowlValue(bowls);
  return bowls.map(row => row.map(v => (v === min ? v + 1 : v)));
};

const distribute = bowls => {
  const dir = [
    [0, 1],
    [1, 0],
    [0, -1],
    [-1, 0],
  ];
  const getNeighbors = (x, y) => dir.map(d => [x + d[0], y + d[1]]);
  const calcDelta = (a, b) => {
    if (typeof a !== 'number' || typeof b !== 'number') return 0;
    const delta = Math.floor(Math.abs(a - b) / 5);
    return a < b ? delta : -delta;
  };
  const getBowlValue = (x, y) => {
    if (x < 0 || y < 0 || bowls[x] === undefined) return undefined;
    return bowls[x][y];
  };

  const deltas = bowls.map((row, x) =>
    row.map((value, y) =>
      sum(
        getNeighbors(x, y).map(([nx, ny]) =>
          calcDelta(value, getBowlValue(nx, ny)),
        ),
      ),
    ),
  );

  return bowls.map((row, i) => row.map((value, j) => value + deltas[i][j]));
};

const rollOnce = (bowls, size) =>
  zip(bowls.slice(size), rotateCW(bowls.slice(0, size)));

const roll = bowls => {
  const rollSize = bowls.filter(row => row.length > 1).length || 1;
  const height = bowls[0].length;
  if (rollSize + height > bowls.length) return bowls;
  return roll(rollOnce(bowls, rollSize));
};

const fold = bowls =>
  zip(
    bowls.slice(bowls.length / 2),
    reverseLR(reverseUD(bowls.slice(0, bowls.length / 2))),
  );
const flat = bowls => bowls.flat().map(v => [v]);

const canFinish = (bowls, k) => maxBowlValue(bowls) - minBowlValue(bowls) <= k;

const solution = function () {
  const [n, k] = input.num();
  let bowls = input.num().map(v => [v]);

  let ans = 0;
  while (!canFinish(bowls, k)) {
    bowls = pipe(
      bowls,
      addFish,
      roll,
      distribute,
      flat,
      fold,
      fold,
      distribute,
      flat,
    );
    ans++;
  }
  console.log(ans);
};

solution();