[백준 / BOJ] 17114번 하이퍼 토마토 (Javascript / Node js)

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

---

문제 해설

이번 하이퍼 토마토 문제는 지난 토마토 문제에서 배열의 깊이가 2차원에서 11차원으로 변형된 심화 문제입니다. 

[백준 / BOJ] 7576번 토마토 ( Node js / Javascript )

 

언뜻 보기에는 11차원이라는 말도 안되는 조건 때문에 괴랄해 보이겠지만 사실은 보이는 것 만큼의 난이도를 가진 문제는 아닙니다. 만약 만약 x축이 이동할 때 동시에 y축도 이동이 가능하다면 문제가 생기겠지만, 해당 문제의 조건에서는 한번의 이동에서 이동 가능한 축은 하나로 제한되어 있기 때문에 사실상 이동 방향의 선택지가 4(2 x 2)개에서 22(11 x 2)개로 늘어났을 뿐이기 때문입니다.

 

그리고, m * n * o * p * q * r * s * t * u * v * w의 값이 10^6으로 제한되어 있는 것을 볼 수 있습니다. 하지만 그럼에도 지난 2차원 배열에서의 로직만으로 시간 제한안에 통과하는 건 당연히 무리가 있었기 때문에, 지난 토마토 문제에서의 코드를 극한으로 최적화해보는 좋은 경험이 되었습니다.

 

BFS에 대한 설명은 2차원 토마토에서 충분히 다뤘기 때문에 이번 문제에서는 2차원 토마토 코드와의 차이점을 중점으로 설명하도록 하겠습니다.

 

생각해낸 개선점은 다음과 같습니다.

1. 지난 코드는 안익은 토마토가 남아있는지 검사하기 위해서 bfs가 끝난 뒤 배열을 한번 더 순회했습니다. 처음 시작점 (1)을 찾는 반복문 내에서 0의 개수를 카운트하여 초기 익지 않은 토마토의 개수를 세고, bfs 동작 과정에서 0을 1로 바꿀때마다 카운트하여 익힌 토마토의 개수를 세어 이 둘이 일치하지 않을 경우 익지 않은 토마토가 존재한다고 판단하도록 개선했습니다.

2. 위 코드에서는 선형 시간 복잡도 O(N)의 shift()연산을 피하기 위해 매 반복마다 nextQueue에 다음에 탐색할 노드들을 담고, queue를 nextQueue 로 교체했었는데, 이번에는 linked list 자료구조를 사용해 Queue를 직접 구현하여 사용했습니다.

 

여기까지는 순조로우나 해결해야 될 부분이 하나 더 남았습니다.

입력값

 

입력 처리 부분에서 2차원 배열의 경우에는 받은 입력을 그대로 사용해도 문제가 없었지만, 이번 문제의 경우는 11차원이기 때문에 2차원으로 받은 배열을 11차원으로 가공해주어야 합니다.

 

예를 들어 입력이 다음과 같을 경우, 5 x 3 짜리 2차원 배열이 2개 있는 것이기 때문에 3줄이 들어왔을 때, 끊어주고 다음 배열에 넣어주는 작업이 필요합니다. 그리고 입력이 5 3 2 2 ... 라면 5 x 3 짜리 2차원 배열이 2개 들어있는 배열이 2개 존재한다는 뜻입니다.

 

이미 3차원 토마토에서 한번 겪어본 맥락이기 때문에 어떻게 해야 될지는 금방 감이 잡혔지만, 11차원을 구현하기 위해 비윤리적으로 늘어난 indent 때문에 생각보다 구현에서 애를 먹었습니다.

 

그렇게 처음 shift() 연산을 사용해서 2차원 배열을 11차원으로 구현했고 시간초과가 발생했습니다. m * n * o * p * q * r * s * t * u * v * w 의 값이 10^6이란건 최악의 경우 m,n,o,p,q,r,s,t,u,v 가 1이고, w가 10^6일 수도 있다는 점을 간과한 것이 문제였습니다.

 

이렇게 w가 10^6일 경우 시간 복잡도 O(N)의 shift()연산을 10^6 수행하게 되니 당연히 시간초과가 발생하게 됩니다.

 

이는 shift()연산을 포인터로 대체하여 해결했습니다.

 

+ shift() 연산이 O(N)의 시간복잡도를 갖는 이유는, [1, 2, 3, 4]라는 배열에서 shift()연산을 수행하게 되면 1만 제거하는 것이 아닌, 1을 제거한 뒤 2, 3, 4를 전부 한칸씩 앞으로 가져와야하기 때문입니다.

 

그렇기 때문에 이를 포인터로 대체하여 배열은 그대로 두고, 포인터가  가르키는 index를 1씩 증가하도록 대체하면 시간복잡도는 O(1)로 개선됩니다.

 

전체 코드

//하이퍼 토마토
class Node {
  constructor(value, next) {
    this.value = value;
    this.next = next;
  }
}

class Queue {
  constructor() {
    this.lastNode = null;
    this.length = 0;
    this.firstNode = null;
  }

  push(v) {
    if (this.length === 0) {
      this.firstNode = new Node(v, null);
      this.lastNode = this.firstNode;
    } else {
      let newNode = new Node(v, null);
      this.lastNode.next = newNode;
      this.lastNode = newNode;
    }
    this.length++;
  }

  pop() {
    if (this.length === 0) return undefined;
    let secondNode = this.firstNode.next;
    let value = this.firstNode.value;
    this.firstNode = secondNode;
    if (this.length === 1) this.lastNode = null;
    this.length--;
    return value;
  }
}

const fs = require('fs');

let [[m, n, o, p, q, r, s, t, u, v, w], ...arr] = fs
  .readFileSync('../../input.txt')
  .toString()
  .trim()
  .split('\n')
  .map((item) => item.split(' ').map((v) => +v));

let map = Array(w)
  .fill(0)
  .map((w_v) =>
    Array(v)
      .fill(0)
      .map((v_v) =>
        Array(u)
          .fill(0)
          .map((u_v) =>
            Array(t)
              .fill(0)
              .map((t_v) =>
                Array(s)
                  .fill(0)
                  .map((s_v) =>
                    Array(r)
                      .fill(0)
                      .map((r_v) =>
                        Array(q)
                          .fill(0)
                          .map((q_v) =>
                            Array(p)
                              .fill(0)
                              .map((p_v) =>
                                Array(o)
                                  .fill(0)
                                  .map((o_v) =>
                                    Array(n)
                                      .fill(0)
                                      .map((n_v) => 0)
                                  )
                              )
                          )
                      )
                  )
              )
          )
      )
  );

let cnt_0 = 0;
let indexes = [];

let arr_index = 0;
for (let i1 = 0; i1 < w; i1++) {
  for (let i2 = 0; i2 < v; i2++) {
    for (let i3 = 0; i3 < u; i3++) {
      for (let i4 = 0; i4 < t; i4++) {
        for (let i5 = 0; i5 < s; i5++) {
          for (let i6 = 0; i6 < r; i6++) {
            for (let i7 = 0; i7 < q; i7++) {
              for (let i8 = 0; i8 < p; i8++) {
                for (let i9 = 0; i9 < o; i9++) {
                  for (let i10 = 0; i10 < n; i10++) {
                    map[i1][i2][i3][i4][i5][i6][i7][i8][i9][i10] =
                      arr[arr_index++];
                    map[i1][i2][i3][i4][i5][i6][i7][i8][i9][i10].forEach(
                      (v, i) => {
                        if (v === 1) {
                          indexes.push([
                            i1,
                            i2,
                            i3,
                            i4,
                            i5,
                            i6,
                            i7,
                            i8,
                            i9,
                            i10,
                            i,
                          ]);
                        }
                        if (v === 0) {
                          cnt_0++;
                        }
                      }
                    );
                  }
                }
              }
            }
          }
        }
      }
    }
  }
}

const directions = [
  [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, -1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, -1, 0, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, -1, 0, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, -1, 0, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, -1, 0, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1],
  [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, -1],
];

let max_day = 0;
const bfs = (start_indexes) => {
  const queue = new Queue();
  start_indexes.forEach((index) => queue.push([...index]));
  while (queue.length > 0) {
    let [i1, i2, i3, i4, i5, i6, i7, i8, i9, i10, i11] = queue.pop();
    directions.forEach(
      ([di1, di2, di3, di4, di5, di6, di7, di8, di9, di10, di11]) => {
        let ni1 = i1 + di1;
        let ni2 = i2 + di2;
        let ni3 = i3 + di3;
        let ni4 = i4 + di4;
        let ni5 = i5 + di5;
        let ni6 = i6 + di6;
        let ni7 = i7 + di7;
        let ni8 = i8 + di8;
        let ni9 = i9 + di9;
        let ni10 = i10 + di10;
        let ni11 = i11 + di11;

        if (
          ni1 >= 0 &&
          ni2 >= 0 &&
          ni3 >= 0 &&
          ni4 >= 0 &&
          ni5 >= 0 &&
          ni6 >= 0 &&
          ni7 >= 0 &&
          ni8 >= 0 &&
          ni9 >= 0 &&
          ni10 >= 0 &&
          ni11 >= 0 &&
          ni1 < w &&
          ni2 < v &&
          ni3 < u &&
          ni4 < t &&
          ni5 < s &&
          ni6 < r &&
          ni7 < q &&
          ni8 < p &&
          ni9 < o &&
          ni10 < n &&
          ni11 < m &&
          map[ni1][ni2][ni3][ni4][ni5][ni6][ni7][ni8][ni9][ni10][ni11] === 0
        ) {
          map[ni1][ni2][ni3][ni4][ni5][ni6][ni7][ni8][ni9][ni10][ni11] =
            map[i1][i2][i3][i4][i5][i6][i7][i8][i9][i10][i11] + 1;
          if (
            map[ni1][ni2][ni3][ni4][ni5][ni6][ni7][ni8][ni9][ni10][ni11] > 0
          ) {
            max_day =
              map[ni1][ni2][ni3][ni4][ni5][ni6][ni7][ni8][ni9][ni10][ni11];
          }
          queue.push([ni1, ni2, ni3, ni4, ni5, ni6, ni7, ni8, ni9, ni10, ni11]);
          cnt_0--;
        }
      }
    );
  }
};

bfs(indexes);

if (max_day === 0) {
  max_day = 1;
}

console.log(cnt_0 > 0 ? -1 : max_day - 1);