[programmers/js] 표 병합

표 병합

https://school.programmers.co.kr/learn/courses/30/lessons/150366

문제 설명

엑셀처럼 동작하는 50×50 크기의 표에서 다음과 같은 명령어들을 수행합니다

• UPDATE r c value: (r, c) 셀의 값을 변경
• UPDATE value1 value2: 값이 value1인 모든 셀을 value2로 변경
• MERGE r1 c1 r2 c2: 두 셀을 병합 (그룹화), 한 셀이 업데이트되면 다른 셀도 함께 값 공유
• UNMERGE r c: 병합된 셀 그룹을 해제하고, (r, c)만 값을 유지
• PRINT r c: 셀의 현재 값을 출력

풀이

이 문제는 유니온 파인드(Disjoint Set Union) 자료구조를 사용하여 해결합니다. 핵심 아이디어는 셀 간 병합 상태를 부모 셀 정보로 관리하는 것입니다.

1. 유니온 파인드 셋업
parents: 각 셀의 부모 좌표를 저장하는 2차원 배열 → parents[r][c] = [pr, pc]
values: 각 셀의 값을 저장하는 2차원 배열 → values[r][c] = "EMPTY"

2. find(r, c)
주어진 셀 (r, c)의 대표 셀(루트)을 찾습니다. 경로 압축(Path Compression)을 통해 탐색 속도를 향상시킵니다.

// 경로 압축을 포함한 find 함수
const find = (r, c) => {
  const [pr, pc] = parents[r][c];
  if (pr === r && pc === c) return [r, c];
  return (parents[r][c] = find(pr, pc));
};

3. union(r1, c1, r2, c2)
두 셀 (r1, c1)과 (r2, c2)를 병합합니다. 병합 시, 대표 셀의 값을 적절히 설정하고, 모든 관련 셀의 부모 정보를 갱신합니다.

// 셀 병합
const union = (r1, c1, r2, c2) => {
  const [p1r, p1c] = find(r1, c1);
  const [p2r, p2c] = find(r2, c2);
  if (p1r === p2r && p1c === p2c) return;

  const val1 = values[p1r][p1c];
  const val2 = values[p2r][p2c];
  const finalVal = val1 !== "EMPTY" ? val1 : val2;
  parents[p2r][p2c] = [p1r, p1c];

  // 같은 그룹의 셀 모두 병합된 대표로 갱신
  for (let i = 1; i < SIZE; i++) {
    for (let j = 1; j < SIZE; j++) {
      const [pi, pj] = find(i, j);
      if (pi === p2r && pj === p2c) {
        parents[pi][pj] = [p1r, p1c];
      }
    }
  }

  values[p1r][p1c] = finalVal;
};

4. unmerge(r, c)
셀 (r, c)가 속한 병합 그룹을 해제합니다. 해당 그룹의 모든 셀을 개별 셀로 분리하고, 값은 "EMPTY"로 초기화합니다. 단, (r, c) 셀은 원래의 값을 유지합니다.

// 셀 병합 해제
const unmerge = (r, c) => {
  const [pr, pc] = find(r, c);
  const original = values[pr][pc];

  for (let i = 1; i < SIZE; i++) {
    for (let j = 1; j < SIZE; j++) {
      if (find(i, j)[0] === pr && find(i, j)[1] === pc) {
        parents[i][j] = [i, j];
        values[i][j] = "EMPTY";
      }
    }
  }

  values[r][c] = original;
};

5. update

const updateAll = (v1, v2) => {
  for (let i = 1; i < SIZE; i++) {
    for (let j = 1; j < SIZE; j++) {
      const [pr, pc] = find(i, j);
      if (values[pr][pc] === v1) {
        values[pr][pc] = v2;
      }
    }
  }
};

const updateOne = (r, c, val) => {
  const [pr, pc] = find(r, c);
  values[pr][pc] = val;
};

최종 코드

function solution(commands) {
  const SIZE = 51;
  const parents = Array.from({ length: SIZE }, (_, r) =>
    Array.from({ length: SIZE }, (_, c) => [r, c])
  );
  const values = Array.from({ length: SIZE }, () => Array(SIZE).fill("EMPTY"));

  const find = (r, c) => {
    const [pr, pc] = parents[r][c];
    if (pr === r && pc === c) return [r, c];
    return (parents[r][c] = find(pr, pc));
  };

  const union = (r1, c1, r2, c2) => {
    const [p1r, p1c] = find(r1, c1);
    const [p2r, p2c] = find(r2, c2);
    if (p1r === p2r && p1c === p2c) return;

    const val1 = values[p1r][p1c];
    const val2 = values[p2r][p2c];
    // 새 그룹의 대표값은 기존 대표값 중 하나
    const finalVal = val1 !== "EMPTY" ? val1 : val2;
    parents[p2r][p2c] = [p1r, p1c];

    // 병합된 모든 셀 찾아서 대표 갱신
    for (let i = 1; i < SIZE; i++) {
      for (let j = 1; j < SIZE; j++) {
        const [pi, pj] = find(i, j);
        if (pi === p2r && pj === p2c) {
          parents[pi][pj] = [p1r, p1c];
        }
      }
    }
    values[p1r][p1c] = finalVal;
  };

  const unmerge = (r, c) => {
    const [pr, pc] = find(r, c);
    const original = values[pr][pc];

    const group = [];
    for (let i = 1; i < SIZE; i++) {
      for (let j = 1; j < SIZE; j++) {
        if (find(i, j)[0] === pr && find(i, j)[1] === pc) {
          parents[i][j] = [i, j];
          values[i][j] = "EMPTY";
        }
      }
    }
    values[r][c] = original;
  };

  const updateAll = (v1, v2) => {
    for (let i = 1; i < SIZE; i++) {
      for (let j = 1; j < SIZE; j++) {
        const [pr, pc] = find(i, j);
        if (values[pr][pc] === v1) {
          values[pr][pc] = v2;
        }
      }
    }
  };

  const updateOne = (r, c, val) => {
    const [pr, pc] = find(r, c);
    values[pr][pc] = val;
  };

  const printCell = (r, c) => {
    const [pr, pc] = find(r, c);
    return values[pr][pc];
  };

  const answer = [];

  for (const cmd of commands) {
    const parts = cmd.split(" ");
    const action = parts[0];

    if (action === "UPDATE") {
      if (parts.length === 4) {
        const [_, r, c, val] = parts;
        updateOne(Number(r), Number(c), val);
      } else {
        const [_, val1, val2] = parts;
        updateAll(val1, val2);
      }
    } else if (action === "MERGE") {
      const [_, r1, c1, r2, c2] = parts;
      union(Number(r1), Number(c1), Number(r2), Number(c2));
    } else if (action === "UNMERGE") {
      const [_, r, c] = parts;
      unmerge(Number(r), Number(c));
    } else if (action === "PRINT") {
      const [_, r, c] = parts;
      answer.push(printCell(Number(r), Number(c)));
    }
  }

  return answer;
}