[프로그래머스 / JAVA / Javascript] 표병합

UnionFind란?

Union Find 란 집합의 원소들이 어느 그룹에 속해 있는지를 빠르게 찾고 (Find) , 합치는 (Union) 연산을 효율적으로 처리하도록 설계된 자료구조이다.

주로 서로소 집합(Disjoint Set) 문제를 해결되는데 사용되는데, 서로소 집합이란 공통된 원소가 없는 두 집합을 의미한다.

기본 연산

Union Find 는 이전에 말했듯이, Find 와 Union 연산을 지원해야 한다.

• Find : 주어진 원소가 속한 대표 를 찾는 연산이다.

int[] find(int x, int y){
        int[] root = this.parents[x][y];
        if(root[0] == x && root[1] == y) return new int[]{x,y};
        int[] newParent = this.find(root[0], root[1]);
        this.parents[x][y] = newParent;

        return newParent;
    }

Union Find 는 이러한 연산을 더욱 효율적으로 하기 위해 경로 압축 을 사용한다. Find 연산시, 현재 노드가 최상위 노드가 아니라면 재귀적으로 부모를 찾아간다. 해당 과정에서 노드의 부모를 최상위 노드로 갱신하여 준다.

• Union : 두 집합을 하나의 집합으로 합치는 연산으로, 두 집합의 대표자를 찾아 비교하고, 정의된 규칙에 따라 한 집합을 다른 집합의 subset 으로 만든다.

문제 풀이

 

프로그래머스 : 표 병합

이 문제는 50 x 50 의 고정 크기 표에서 여러 명령어를 수행하는 프로그램을 작성하는것이 목표다. 표의 각 cell 은 문자열 값을 가질 수 있고, 각 cell 간의 병합 혹은 해제를 수행할 수 있다. 병합된 cell 은 하나의 cell 처럼 동작하며, 병합 된 cell 중 하나라도 update 를 하게 되면, 나머지 cell 들도 동일한 값을 가지게 된다.

그렇다면 어떻게 이 문제를 풀어야 할까?

우선 우리가 관리해야 할 정보는 2가지 이다.

• 각 cell 이 속한 집합 (병합)
• 각 cell 의 상태 (값)

문제의 특성상 merge, unmerge, update 가 여러번 일어날 수 있는데, 그렇다면 이러한 연산들을 빠르게 수행할 수 있는 자료구조인 Union Find를 사용하면 좋겠다는 것을 알 수 있다.
각 cell 을 node로, merge 된 cell 들은 하나의 집합으로 관리하게 되면, 해당 문제를 효율적으로 풀 수 있다.

JAVA

import java.util.ArrayList;

class UnionFind{
    int[][][] parents; // 각 cell 의 부모 좌표를 저장한다. parents[i][j][0] 은 i, j cell 의 부모 x 좌표를 나타낸다
    String[][] value; // 각 cell 이 실제로 가지는 값을 나타낸다.
    UnionFind(){
        this.parents = new int[51][51][2];
        this.value = new String[51][51];

        for(int i = 0; i<51; i++){
            for(int j = 0; j<51; j++){
                this.parents[i][j][0] = i;
                this.parents[i][j][1] = j;
                this.value[i][j] = "";
            }
        }
    }

    int[] find(int x, int y){
        int[] root = this.parents[x][y];
        if(root[0] == x && root[1] == y) return new int[]{x,y};
        int[] newParent = this.find(root[0], root[1]);
        this.parents[x][y] = newParent; // 경로 압축

        return newParent;
    }

    void merge(int x1, int y1, int x2, int y2){
        int[] root1 = this.find(x1, y1);
        int[] root2 = this.find(x2, y2);

        if(root1[0] == root2[0] && root1[1] == root2[1]) return;

        if(!this.value[root1[0]][root1[1]].equals("")){
            this.parents[root2[0]][root2[1]] = new int[]{root1[0], root1[1]};
        }else{
            this.parents[root1[0]][root1[1]] = new int[]{root2[0], root2[1]};
        }
    }

    void unmerge(int x, int y){
        int[] root = this.find(x,y);
        String originalValue = this.value[root[0]][root[1]];


        ArrayList<int[]> toUnmerge = new ArrayList<>();
        for(int i = 0; i<51; i++){
            for(int j = 0; j<51; j++){
                int[] tmp = this.find(i, j);
                if(root[0] == tmp[0] && root[1] == tmp[1]){
                    int[] cur = new int[]{i,j};
                    toUnmerge.add(cur);
                }
            }
        }

        for(int[] un : toUnmerge){
            this.parents[un[0]][un[1]][0] = un[0];
            this.parents[un[0]][un[1]][1] = un[1];
            this.value[un[0]][un[1]] = "";

        }

        this.value[x][y] = originalValue;
    }

    void updateValue(String oldVal, String newVal){
        for(int i = 0; i<51; i++){
            for(int j = 0; j<51; j++){
                if(this.value[i][j].equals(oldVal)){
                    this.value[i][j] = newVal;
                }
            }
        }
    }

    void updateCell(int x, int y, String value){
        int[] root = this.find(x, y);
        this.value[root[0]][root[1]] = value;
    }

    String print(int x, int y){
        int[] root = this.find(x,y);
        return this.value[root[0]][root[1]].equals("") ? "EMPTY" : this.value[root[0]][root[1]];
    }

}

class Solution {
    public String[] solution(String[] commands) {

        UnionFind uf = new UnionFind();
        ArrayList<String> ans = new ArrayList<>();

        for(String command: commands){
            String[] c = command.split(" ");

            if(c[0].equals("UPDATE")){
                if(c.length == 4){
                    int x = Integer.parseInt(c[1]);
                    int y = Integer.parseInt(c[2]);
                    uf.updateCell(x, y, c[3]);
                }else{
                    uf.updateValue(c[1], c[2]);
                }
            }else if(c[0].equals("MERGE")){
                int x1 = Integer.parseInt(c[1]);
                int y1 = Integer.parseInt(c[2]);
                int x2 = Integer.parseInt(c[3]);
                int y2 = Integer.parseInt(c[4]);
                uf.merge(x1,y1,x2,y2);
            }else if(c[0].equals("UNMERGE")){
                int x = Integer.parseInt(c[1]);
                int y = Integer.parseInt(c[2]);
                uf.unmerge(x, y);
            }else if(c[0].equals("PRINT")){
                int x = Integer.parseInt(c[1]);
                int y = Integer.parseInt(c[2]);
                String res = uf.print(x, y);
                ans.add(res);
            }
        }

        String[] answer = new String[ans.size()];
        for(int i = 0; i<answer.length; i++){
            answer[i] = ans.get(i);
        }

        return answer;
    }

}

JAVASCRIPT

/*
  UPDATE r c value : (r, c) 의 cell 을 value로 

  UPDATE value1 value2 : value1 인 모든 cell 을 value2 로

  MERGE r1 c1 r2 c2 : (r1, c1) 과 (r2, c2) cell 을 병합

  UNMERGE r c : (r, c) cell 병합 해제

  PRING r c : (r, c) 출력


*/
class UnionFind{
  constructor(){
    this.parents = [];
    this.value = [];

    for(let i = 0; i<51; i++){
      this.parents[i] = [];
      this.value[i] = [];

      for(let j = 0; j<51; j++){
        this.value[i][j] = "";
        this.parents[i][j] = [i,j];
      }
    }
  }

  find(x, y){
    const [parentX, parentY] = this.parents[x][y];
    if(parentX === x && parentY === y) return [x, y];
    return this.parents[x][y] = this.find(parentX, parentY);
  }

  merge(x1, y1, x2, y2){
    const [rootX1, rootY1] = this.find(x1, y1);
    const [rootX2, rootY2] = this.find(x2, y2);

    if(rootX1 === rootX2 && rootY1 === rootY2) return;

    if(this.value[rootX1][rootY1] !== ""){
      this.parents[rootX2][rootY2] = [rootX1, rootY1];
    }else{
      this.parents[rootX1][rootY1] = [rootX2, rootY2];
    }
  }

  unmerge(x, y){
    const [rootX, rootY] = this.find(x, y);
    const originalValue = this.value[rootX][rootY];

    const toUnmerge = [];
    for(let i = 0; i<51; i++){
      for(let j =0; j<51; j++){
        let tmp = this.find(i,j);
        if(rootX === tmp[0] && rootY === tmp[1]) toUnmerge.push([i,j]);
      }
    }

    toUnmerge.forEach(([i,j]) => {
      this.parents[i][j] = [i,j];
      this.value[i][j] = "";
    })
    this.value[x][y] = originalValue;
  }

  updateValue(oldVal, newVal){
    for(let i = 0; i<51; i++){
      for(let j = 0; j<51; j++){
        if(this.value[i][j] === oldVal) this.value[i][j] = newVal;
      }
    }
  }

  updateCell(x, y, value){
    const [rootX, rootY] = this.find(x,y);
    this.value[rootX][rootY] = value;
  }

  print(x, y){
    const [rootX, rootY] = this.find(x, y);
    return this.value[rootX][rootY] === "" ? "EMPTY" : this.value[rootX][rootY];
  }
}

function solution(commands) {
  var answer = [];
  const uf = new UnionFind();

  for(let command of commands){
    let c = command.split(" ");

    if(c[0] === "UPDATE"){
      if(c.length === 4){
        uf.updateCell( parseInt(c[1],10), parseInt(c[2],10), c[3]);
      }else{
        uf.updateValue(c[1], c[2]);
      }
    }else if(c[0] === "MERGE"){

      uf.merge(
        parseInt(c[1], 10),
        parseInt(c[2], 10),
        parseInt(c[3], 10),
        parseInt(c[4], 10)
      );

    }else if(c[0] === "UNMERGE"){
      uf.unmerge(
        parseInt(c[1], 10),
        parseInt(c[2], 10)
      );
    }else{
      answer.push(uf.print(parseInt(c[1], 10) , parseInt(c[2], 10)));
    }
  }
  return answer;
}