[JS] 지형 이동

union-find를 응용해서 해결하였다.

 

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

프로그래머스

 

 

사실 어느정도 문제에서 힌트(?)가 있다. 아래와 같이 일종의 팀을 짜는 것이 중요하다. 즉, 서로 건너건너서 사다리 없이 갈 수 있는 공간을 한 팀이라고 생각했다. 이런경우 바로 떠오르는 방법이 유니온-파인드 알고리즘이었다.

 

 

따라서 문제푸는 방법자체는 아래와 같이 간단하게 정리되었다.

 

1. 유니온-파인드로 팀분리하기

2. 팀에서 다른팀으로 넘어가는 최소비용을 등록하기

3. 최소비용을 정렬하기

4. 최소비용순으로 사다리를 놓기 ( 이미 연결된 팀이라면 패스 )

 

사다리를 정렬할 때 아래와 같이 객체를 활용하여 정렬하였다.

{
    from : '0,0',
    to : '1,0',
    diff : 3
}

 

2차원 유니온-파인드 구조를 활용했기 때문에 위치가 배열로 나오는데 이를 map자료형에 쓰면 다른 객체로 인식해서 string화해서 키로 써주었다

 

 

 

 

const isSameAry = (a,b) => a[0]===b[0]&&a[1]===b[1]

const find = (a,parent) => {
    const parentA=parent[a[0]][a[1]]
    if(isSameAry(a,parentA)) return a
    return parent[a[0]][a[1]] = find(parentA,parent)
}

const union = (a,b,parent) => {
    a = find(a,parent)
    b = find(b,parent)
    
    if(a>b) parent[a[0]][a[1]] = b
    else parent[b[0]][b[1]] = a
    
}



function solution(land, height) {
    const {length} = land
    const dc = [1,0,-1,0]
    const dr = [0,1,0,-1]
    
    const parent = [...Array(length)].map((_,i) => [...Array(length)].map((_,j)=>[i,j]))
    
    const isCanGo = (r,c) => 0<=r&&r<length&&0<=c&&c<length
    //union,find로 팀을 합침
    for(let i = 0 ; i < length ; i++){
        for(let j = 0 ; j < length; j++){
            for(let d = 0 ; d < 4 ; d++){
                const [nR,nC] = [i+dr[d],j+dc[d]]
                if(!isCanGo(nR,nC)) continue
                if(Math.abs(land[i][j]-land[nR][nC])<=height){
                    union([i,j],[nR,nC],parent)
                }
            }
        }
    }
    
    //각 팀별 이동할 수 있는 사다리의 최소값을 그래프 형식으로 정리
    const connectMap = new Map()
   
    for(let i = 0 ; i< length; i++){
        for(let j = 0 ; j < length ; j ++){
            const [r,c]= find([i,j],parent)
            for(let d = 0 ; d < 4 ; d++){
                const [nR,nC] = [i+dr[d],j+dc[d]]
                if(!isCanGo(nR,nC)) continue
                const [pnR,pnC] = find([nR,nC],parent)
                if(isSameAry([r,c],[pnR,pnC])) continue
                const diff = Math.abs(land[nR][nC]-land[i][j])
                const key = String([r,c])
                
                if(!connectMap.has(key)) {
                    connectMap.set(key,[{to:String([pnR,pnC]),diff}])
                } else {
                    const team = connectMap.get(key).find(v => v.to===String([pnR,pnC]))
                    if(!team) connectMap.get(key).push({to:String([pnR,pnC]),diff})
                    else if(team.diff>diff) team.diff=diff
                }
            }
        }
    }
    
    //가장 작은 사다리 비용부터 정리
    const diffInfo = []
    for(const [from, diffs] of connectMap){
        for(const {to,diff} of diffs){
            diffInfo.push([from,to,diff])
        }
    }
    diffInfo.sort((a,b) => a[2]-b[2])
    
    let ret = 0
    
    //가장 작은 사다리 비용부터 순차적으로 합쳐나가기
    for(let [from,to,diff] of diffInfo){
        from = from.split(',').map(v=>+v)
        to = to.split(',').map(v=>+v)
        if(isSameAry(find(from,parent),find(to,parent))) continue
        ret += diff
        union(from,to,parent)
    }
    return ret
    
}