[프로그래머스][union find] 셀 병합

     

목차

 

 

문제

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

프로그래머스

 

 

 

문제 구현 방향

union find로 구현하는 문제였다. 이 때 주의할점은 데이터의 정합성을 유지하기 위해서는 표를 union 으로 합친뒤 루트 노드만 value를 넣고 나머지는 empty로 만들어 주어야 한다.

 

 

아이디어

이차원 좌표를 r*50+c 이런식으로 일차원으로 만들면 더 쉽게 접근할 수 있다.

이 때 문자열 분리한 뒤 숫자로 바꿔주는 거 주의하자

 

 

 

또한 unmerge할때 주의를 해야 한다.

처음에 아래와 같이 코드를 짰는데 각 경우에 대해 인덱스를 찾기 전에 union의 경로를 바꾸어 버리기 때문에 

오류가 난다.

    else if (cmd[0] === "UNMERGE") {
      const [, r, c] = cmd;
      const target = idx(+r, +c);
      const root = find(target);
      const rootValue = values[root];

      for(let i=0; i< SIZE*SIZE; i++){
          if(find(i) === root){
              parent[i] = i;
              values[i] = 'EMPTY';
          }
      }
      values[target] = rootValue;
    }

 

따라서 각 경우에 대해 인덱스를 찾어 배열에 모아 둔 뒤 union 경로를 바꾸어야 한다.

  else if (cmd[0] === "UNMERGE") {
      const [, r, c] = cmd;
      const target = idx(+r, +c);
      const root = find(target);
      const rootValue = values[root];

      const group = [];
      for (let i = 0; i < parent.length; i++) {
        if (find(i) === root) group.push(i);
      }
      for (const g of group) {
        parent[g] = g;
        values[g] = "EMPTY";
      }
      values[target] = rootValue;
    }

 

 

 

코드 구현

function solution(commands) {
  const SIZE = 51;
  const parent = Array(SIZE * SIZE).fill(0).map((_, i) => i);
  const values = Array(SIZE * SIZE).fill("EMPTY");
  const answer = [];

  const idx = (r, c) => r * SIZE + c;

  function find(a) {
    if (parent[a] === a) return a;
    return find(parent[a]);
  }

  function union(a, b) {
    const pa = find(a);
    const pb = find(b);
    if (pa === pb) return;

    let mergedValue = "EMPTY";
    if (values[pa] !== "EMPTY" && values[pb] !== "EMPTY") {
      mergedValue = values[pa];
    } else if (values[pa] !== "EMPTY") {
      mergedValue = values[pa];
    } else if (values[pb] !== "EMPTY") {
      mergedValue = values[pb];
    }

    parent[pa] = pb;
    values[pa] = "EMPTY";
    values[pb] = mergedValue;
  }

  for (const command of commands) {
    const cmd = command.split(" ");

    if (cmd[0] === "UPDATE") {
      if (cmd.length === 4) {
        const [, r, c, value] = cmd;
        const root = find(idx(+r, +c));
        values[root] = value;
      } else {
        const [, v1, v2] = cmd;
        for (let i = 0; i < values.length; i++) {
          if (values[i] === v1) values[i] = v2;
        }
      }
    }

    else if (cmd[0] === "MERGE") {
      const [, r1, c1, r2, c2] = cmd;
      union(idx(+r1, +c1), idx(+r2, +c2));
    }

     else if (cmd[0] === "UNMERGE") {
      const [, r, c] = cmd;
      const target = idx(+r, +c);
      const root = find(target);
      const rootValue = values[root];

      const group = [];
      for (let i = 0; i < parent.length; i++) {
        if (find(i) === root) group.push(i);
      }
      for (const g of group) {
        parent[g] = g;
        values[g] = "EMPTY";
      }
      values[target] = rootValue;
    }

    else if (cmd[0] === "PRINT") {
      const [, r, c] = cmd;
      const root = find(idx(+r, +c));
      answer.push(values[root]);
    }
  }

  return answer;
}