[프로그래머스] 표 병합

📙 1. 문제

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

문제 설명

 풀이 1

풀이 과정

: Union-Find알고리즘을 이용한 문제

1. cell배열과 parent 배열
cell 배열 : 51x51 크기의 2차원 배열로, 각 셀에 할당된 문자열 값을 저장

parent 배열 : 51x51 크기의 2차원 배열로, 각 셀의 부모 셀(병합이 일어난 경우 해당 셀이 속한 그룹의 대표 셀)의 좌표를 저장

2. 각 기능들을 함수화해주어, 추상화하였다.

- iterateAll(callbackFn) : 모든 셀에 대해 주어진 콜백 함수를 실행

- find(coord) : 좌표 [r,c]를 찾는

- isSameCoords([r,c],parent[r][c])

function solution(commands) {
  let answer = [];
  const cell = Array(51)
    .fill()
    .map((_) => Array(51).fill(''));
  const parent = Array(51)
    .fill()
    .map((_, i) =>
      Array(51)
        .fill()
        .map((_, j) => [i, j])
    );

  for (const commandStr of commands) {
    const [command, ...rest] = commandStr.split(' ');

    switch (command) {
      case 'UPDATE':
        if (rest.length === 3) update(rest);
        else replace(rest);
        break;
      case 'MERGE':
        merge(rest);
        break;
      case 'UNMERGE':
        unmerge(rest);
        break;
      case 'PRINT':
        answer = [...answer, print(rest)];
        break;
    }
  }

  return answer;

  function update(param) {
    const [r, c, value] = param;
    const target = find([r, c]);

    iterateAll((i, j) => {
      if (isSameCoords(parent[i][j], target)) cell[i][j] = value;
    });
  }

  function replace(param) {
    const [value1, value2] = param;

    iterateAll((i, j) => {
      if (cell[i][j] === value1) cell[i][j] = value2;
    });
  }

  function merge(param) {
    const [r1, c1, r2, c2] = param;
    if (r1 === r2 && c1 === c2) return;

    const value = cell[r1][c1] !== '' ? cell[r1][c1] : cell[r2][c2];
    const parent1 = find([r1, c1]);
    const parent2 = find([r2, c2]);

    if (!isSameCoords(parent1, parent2)) {
      parent[r2][c2] = parent1;
    }

    iterateAll((i, j) => {
      if (isSameCoords(parent[i][j], parent2)) {
        parent[i][j] = parent1;
      }
      if (isSameCoords(parent[i][j], parent1)) {
        cell[i][j] = value;
      }
    });
  }

  function unmerge(param) {
    const [r, c] = param;
    const value = cell[r][c];
    const target = find([r, c]);

    iterateAll((i, j) => {
      if (isSameCoords(parent[i][j], target)) {
        cell[i][j] = '';
        parent[i][j] = [i, j];
      }
    });

    cell[r][c] = value;
  }

  function print(param) {
    const [r, c] = param;

    return cell[r][c] === '' ? 'EMPTY' : cell[r][c];
  }

  function find(coord) {
    const [r, c] = coord;

    if (isSameCoords([r, c], parent[r][c])) {
      return [Number(r), Number(c)];
    }

    parent[r][c] = find(parent[r][c]);

    return parent[r][c];
  }

  function isSameCoords(coord1, coord2) {
    return coord1.toString() === coord2.toString();
  }

  function iterateAll(callbackFn) {
    for (let i = 0; i < 51; i++) {
      for (let j = 0; j < 51; j++) {
        callbackFn(i, j);
      }
    }
  }
}

---

🤔 2. 느낀 점

어렵다.

 

🤩 3. 한 번 더 짚고 갈 점

50x50의 빈 배열 : Array(50).fill().map((_)=>Array(51).fill(''))

50x50의 index로 채운 배열 : Array(50).fill().map((_,i)=>Array(50).fill().map((_,j)=>[i,j))

Union-Find 알고리즘

• Disjoin Set : 서로 중복되지 않는 부분 집합들로 나눠진 원소들에 대한 정보를 저장하고 조작하는 자료구조
• 공통 원소가 없는, 즉 '상호 배타적'인 부분 집합들로 나눠진 원소들에 대한 자료구조
• Unifon-Find : Disjoint Set을 표현할 때 사용하는 알고리즘
  • make-set(x) : 초기화, x를 유일한 원소로하는 새로운 집합을 만듬
  • union(x,y) : 합하기, x가 속한 집합과 y가 속한 집합을 합침
  • find(x) : 찾기, x가 속한 집합의 대표값(루트 노드 값)을 반환. x가 어떤 집합에 속해 있는지 찾는 연산

참고 : Union-Find