[프로그래머스] 가장 큰 삼각형 덩어리 (JavaScript)

문제 설명[링크]

N행 M열의 2차원 격자 grid가 주어집니다. 격자의 각 칸은 한 변의 길이가 √2인 정사각형이며, 각 칸 안에는 대각선이 하나 그어져 있습니다. 이 대각선은 / 방향(1) 또는 \ 방향(-1) 중 하나입니다.

각 정사각형 칸은 대각선에 의해 동일한 크기의 직각삼각형 두 개로 나뉘며, 당신은 각 칸에서 두 삼각형 중 정확히 하나만 색칠할 수 있습니다. 색칠된 삼각형들은 한 '변'을 공유해야 서로 연결되며, 이렇게 연결된 삼각형들의 집합을 하나의 삼각형 덩어리라고 합니다.

당신의 목표는 격자 전체를 적절히 색칠하여, 연결된 하나의 삼각형 덩어리 중 가능한 가장 큰 덩어리의 넓이를 구하는 것입니다. 각 삼각형의 넓이는 칸을 이루는 정사각형의 면적(2)의 절반인 1입니다. 따라서 덩어리에 포함된 삼각형의 개수가 곧 그 덩어리의 넓이가 됩니다.

격자의 상태를 나타내는 2차원 정수 배열 grid가 매개변수로 주어집니다. 이 격자를 적절히 색칠했을 때, 만들 수 있는 삼각형 덩어리들 중에서 가장 넓이가 큰 덩어리의 넓이를 return 하도록 solution 함수를 완성해 주세요.

풀이

• 각 셀은 왼쪽, 오른쪽 기준으로 나눔
• 각 칸은 좌/상 or 우/하 로 갈 수 있는 연결 그래프 형태(탐색 가능)
• 일반적인 탐색처럼 x,y +-1로 가는 탐색이 아니므로, 다음 노드를 구하는 함수 구현
• 한번의 탐색으로 갈 수 있는 모든 칸을 구함
  • 해당 칸은 무조건 순환하거나 1자형 길이 됨
• 그러한 길들의 x, y 좌표를 수집 후 배열에 순서대로 저장
• 순서대로 저장된 길을 투포인터로 2개의 동일한 점을 지나지 않게 하는 최대 길이를 구함
• 만약 순환한다면, 돌 수 있으므로 배열 * 2 해줌 (단, 임계값 설정 후 넘지 않는지 체크 필요)

function solution(grid) {
  const n = grid.length;
  const m = grid[0].length;
  let visCount = -1;
  const visited = new Array(n)
    .fill()
    .map(() => new Array(m).fill().map(() => new Array(2).fill(-1)));

  function getNexts(i, j, k) {
    const nexts = [];
    const flag = grid[i][j];
    if (flag === 1) {
      if (k === 0) {
        if (j !== 0) nexts.push([i, j - 1, 1]);
        if (i !== 0) {
          const aFlag = grid[i - 1][j];
          if (aFlag === 1) nexts.push([i - 1, j, 1]);
          else nexts.push([i - 1, j, 0]);
        }
      } else {
        // k === 1
        if (j !== m - 1) nexts.push([i, j + 1, 0]);
        if (i !== n - 1) {
          const aFlag = grid[i + 1][j];
          if (aFlag === 1) nexts.push([i + 1, j, 0]);
          else nexts.push([i + 1, j, 1]);
        }
      }
    } else {
      // flag === -1
      if (k === 0) {
        if (j !== 0) nexts.push([i, j - 1, 1]);
        if (i !== n - 1) {
          const aFlag = grid[i + 1][j];
          if (aFlag === 1) nexts.push([i + 1, j, 0]);
          else nexts.push([i + 1, j, 1]);
        }
      } else {
        // k === 1
        if (j !== m - 1) nexts.push([i, j + 1, 0]);
        if (i !== 0) {
          const aFlag = grid[i - 1][j];
          if (aFlag === 1) nexts.push([i - 1, j, 1]);
          else nexts.push([i - 1, j, 0]);
        }
      }
    }
    return nexts;
  }

  function calculate(merged, isCycle) {
    if (!merged.length) return 0;
    let limit = merged.length;
    const dupCheckSet = new Set();
    let isDupExist = false;
    for (const el of merged) {
      if (dupCheckSet.has(el)) {
        isDupExist = true;
        break;
      }
      dupCheckSet.add(el);
    }
    if (isDupExist) limit--;

    let ret = 0;
    if (isCycle) {
      const dup = [...merged];
      for (const el of merged) dup.push(el);
      merged = dup;
    }
    let left = 0;
    const memo = new Map();
    let dupCounts = 0;
    const addMemo = el => {
      if (!memo.has(el)) {
        memo.set(el, 1);
        return;
      }
      const v = memo.get(el);
      if (v === 1) dupCounts++;
      memo.set(el, v + 1);
    };
    const checkCondition = () => {
      return dupCounts < 1;
    };
    const removeMemo = el => {
      const v = memo.get(el);
      if (v === 2) dupCounts--;
      if (v === 1) memo.delete(el);
      else memo.set(el, v - 1);
    };

    for (let right = 0; right < merged.length; right++) {
      addMemo(merged[right]);
      while (!checkCondition()) {
        removeMemo(merged[left]);
        left++;
      }
      ret = Math.max(ret, right - left + 1);
    }

    return Math.min(limit, ret);
  }

  function go(i, j, k) {
    const acc = [];
    if (visited[i][j][k] === visCount) return acc;
    const key = i * m + j;
    acc.push(key);
    let queue = [[i, j, k]];
    visited[i][j][k] = visCount;
    while (queue.length) {
      const newQueue = [];
      for (const [x, y, z] of queue) {
        const nexts = getNexts(x, y, z);
        for (const next of nexts) {
          const [nx, ny, nz] = next;
          if (visited[nx][ny][nz] !== visCount) {
            acc.push(nx * m + ny);
            newQueue.push(next);
            visited[nx][ny][nz] = visCount;
          }
        }

        queue = newQueue;
      }
    }
    return acc;
  }

  function check(i, j, k) {
    const nexts = getNexts(i, j, k);
    visited[i][j][k] = ++visCount;
    if (!nexts.length) return 1;
    const results = nexts.map(([x, y, z]) => {
      return go(x, y, z);
    });
    const isCycle = results.length === 2 && results[1].length === 0;
    const merged = results[0];
    merged.reverse();
    merged.push(i * m + j);
    if (results.length === 2) {
      for (const el of results[1]) {
        merged.push(el);
      }
    }

    return calculate(merged, isCycle);
  }

  let res = 0;

  for (let i = 0; i < n; i++) {
    for (let j = 0; j < m; j++) {
      for (let k = 0; k < 2; k++) {
        if (visited[i][j][k] === -1) {
          res = Math.max(res, check(i, j, k));
        }
      }
    }
  }

  return res;
}