[JS] 표 병합

표 병합을 주제로 한 구현문제였다.

 

딱 문제를 보자마자 떠오른 생각이 union-find 를 활용하자였다.

 

따라서 병합된 표를 구현하기 위해서 union-find 알고리즘을 응용하였다. 2차원 배열의 unionfind를 통해 셀을 구현하고 문제에서 주어진 명령어들을 구현하였다.

 

1. merge

  union-find 알고리즘에서 union 단계를 수행한다. 더 작은 수를 가진 쪽이 부모가 되게 했다.

2. update 

  단순히 cell의 내용을 바꿔주면 된다. 이후 명령어 처리가 편하도록 인자의 개수가 2개,3개에 따라 다른 함수가 호출되도록 구현하였다.

3.  unMerge

  r,c 로 들어온 셀의 부모 요소를 가지고 있는 모든 셀을 초기화해준다.

  이때 초기화를 해주면서 탐색하면 연결고리가 끊어지는 경우가 있어서 부모 요소를 모두 탐색부터 해준 후에 초기화를 진행해야 오류가 나지 않는다.

4. print

  문제상에서는 출력을 해야 하지만 정답배열에 추가하는 로직으로 구현해주었다.

 

 

 

 

 

function solution(commands) {
    const cell = [...Array(51)].map(v => [...Array(51)].fill("EMPTY"))
    const parents = [...Array(51)].map((_,i) => [...Array(51)].map((_,j)=>[i,j]))
    const ret = []
    
    const find = ([aI,aJ]) => {
        if (parents[aI][aJ][0] === aI && parents[aI][aJ][1]===aJ) return [aI,aJ]
        else return find(parents[aI][aJ])
    }

    const merge = (a , b) => {
        const [aI,aJ] = find(a)
        const [bI,bJ] = find(b)
        const value = cell[aI][aJ]==="EMPTY" ? cell[bI][bJ] : cell[aI][aJ]
    
        if ([aI,aJ]<[bI,bJ]) parents[bI][bJ] = [aI,aJ]
        else parents[aI][aJ] = [bI,bJ]
        
        cell[aI][aJ] = value
        cell[bI][bJ] = value
    }
    
    const updateByCoord = (r,c,value) => {
        const [pR,pC] =find([+r,+c]) 
        cell[pR][pC] = value
    }
    
    const updateByValue = (value1,value2) => {
        for (let i = 1 ; i <=50 ; i++) {
            for (let j = 1 ; j <= 50 ; j++){
                const [pI,pJ] = find([i,j])
                if (cell[pI][pJ]===value1) cell[pI][pJ] = value2
            }
        }
    }
    
    function update () {
        if (arguments.length===3) updateByCoord(...arguments)
        else updateByValue(...arguments)
    }
    
    const unMerge = (r,c) => {
        r = +r , c = +c
        const [pR,pC] = find([r,c])
        const value = cell[pR][pC]
        const mergedList = []
        for (let i = 1 ; i <= 50 ; i++) {
            for (let j = 1 ; j <= 50 ; j++){
                const [pI,pJ] = find([i,j])
                if (pR===pI && pC === pJ)
                    mergedList.push([i,j])
            }
        }
        
        for (const [i,j] of mergedList){
            parents[i][j] = [i,j]
            cell[i][j] = "EMPTY"
        }
        cell[r][c] = value
    }
    
    
    const print = (r,c) => {
        const [pR,pC] = find([+r,+c])
        ret.push(cell[pR][pC])
    }
    
    for (const command of commands){
        const [type,...arg] = command.split(" ")
        switch(type){
            case("UPDATE"):
                update(...arg)
                break
            case("MERGE"):
                const [aI,aJ,bI,bJ] = arg
                merge([+aI,+aJ],[+bI,+bJ])
                break
            case("UNMERGE"):
                unMerge(...arg)
                break
            case("PRINT"):
                print(...arg)
                break
            default:
                console.log('wrong command')
        }
        
        
    }
    return ret
    
}