[프로그래머스] 표 병합

😀요점

1. 유니온 파인드 사용

2. 노드 A, 노드 B, 노드 C가 있을 때
   B가 C의 부모인 상태에서 A와 C를 병합하려고 하면
   B와 C의 부모를 모두 업데이트해 주어야 합니다. C의 부모만 A로 수정하면 문제가 발생합니다. YEON

😎풀이

class TableProgram {
    constructor() {
        this.table = Array.from({length: 51}, () => Array(51).fill(null));
        this.parent = Array.from({length: 51}, (_, i) => Array.from({length: 51}, (_, j) => [i, j]));
        this.result = []
    }

    find(r, c) {
        if (this.parent[r][c][0] !== r || this.parent[r][c][1] !== c) {
            this.parent[r][c] = this.find(this.parent[r][c][0], this.parent[r][c][1]);
        }
        return this.parent[r][c];
    }
     
    insert(r, c, value) {
        const [pR, pC] = this.find(r, c);
        this.table[pR][pC] = value;
    }
    
    update(val1, val2) {
        for(let i = 0; i < this.table.length; i++) {
            for(let j = 0; j < this.table[i].length; j++) {
                const [pR, pC] = this.find(i, j);
                if(this.table[pR][pC] === val1) this.table[pR][pC] = val2;
            }
        }
    }
    
    merge(r1, c1, r2, c2) {
        if(r1 === r2 && c1 === c2) return;

        const [pR1, pC1] = this.find(r1, c1);
        const [pR2, pC2] = this.find(r2, c2);

        if (pR1 === pR2 && pC1 === pC2) return;

        for(let i = 0 ; i < this.parent.length ; i ++) {
            for(let j = 0 ; j < this.parent[i].length ; j ++) {
                if(this.parent[i][j][0] === pR2 && this.parent[i][j][1] === pC2) {
                    this.parent[i][j] = [pR1, pC1];
                }
            }
        }

        if (this.table[pR1][pC1] || this.table[pR2][pC2]) {
            const newValue = this.table[pR1][pC1] || this.table[pR2][pC2];
            this.table[pR1][pC1] = newValue;
            this.table[pR2][pC2] = newValue;
        }
    }


    
    unMerge(r, c) {
        const [pR, pC] = this.find(r, c);
        const oldValue = this.table[pR][pC];
        for(let i = 0 ; i < this.parent.length ; i ++) {
            for(let j = 0 ; j < this.parent[i].length ; j ++) {
                if(this.parent[i][j][0] === pR && this.parent[i][j][1] === pC) {
                    this.parent[i][j] = [i, j];
                    this.table[i][j] = null;
                }
            }
        }
        this.table[r][c] = oldValue;
    }

    
    print(r, c) {
        const [pR, pC] = this.find(r, c);
        const printedVal = this.table[pR][pC] ?? "EMPTY";
        this.result.push(printedVal);
    }
}

function solution(commands) {
    const table = new TableProgram();
    commands.forEach((command) => {
        const splittedCmd = command.split(" ")
        const type = splittedCmd[0]
        const options = splittedCmd.slice(1)
        switch(type) {
            case "UPDATE": {
                const isInsert = options.length === 3
                if(isInsert) table.insert(...options)
                else table.update(...options)
                break
            }
            case "MERGE": {
                table.merge(...options)
                break
            }
            case "UNMERGE": {
                table.unMerge(...options)
                break
            }
            case "PRINT": {
                table.print(...options)
                break
            }
            default:
                break
        }
    })
    return table.result
}