지형 이동

programmers.co.kr/learn/courses/30/lessons/62050

코딩테스트 연습 - 지형 이동

- 문제 내용 : cost를 갖고 있는 cell로 구성이된 grid 에서 주어진 height 이내의 cell끼리는 이동이 가능하다. 이동이 불가능한 cell들이 존재 하는 zone으로는 사다리를 놓고 이동 할 수 있다. 최소한의 사다리 cost로 모든 cell을 순회 가능한 값을 찾아라.

- 접근 방법 : 0,0을 기준으로 height 이내 cell을 모두 순회한다. 순회하는 도중에 접근이 불가능한 주변 cell을 Priority Queue에 집어 넣고 더이상 cell 순회가 불가능 할 경우, Priority Queue에서 가장 차이가 작은 cell을 순회 한다. 이때 cost를 추가 한다.

• 한번 접근을 한 cell은 다시 접근 하지 못하게 해야한다.
• 주어진 height 이내의 순환이 최우선이고 순환이 완료 되면 Priority Queue를 사용한다.
• Priority Queue의 값은 모두 소진 될 때까지 순회가 계속 되어야 한다.

Javascript에는 Priority Queue 내장 객체가 없어서, 이런 문제 풀때는 접근이 어렵다. 

class PriorityQ {
    constructor() {
        this.arr = new Array();
        this.arr.push('');
    }

    push(cost, elem) {
        this.arr.push([cost, elem]);
        let curPosition = this.arr.length-1;

        while (1 < curPosition && this.arr[curPosition][0] < this.arr[Math.floor(curPosition / 2)][0]) {
            let tmp = this.arr[Math.floor(curPosition / 2)];
            this.arr[Math.floor(curPosition / 2)] = this.arr[curPosition];
            this.arr[curPosition] = tmp;
            curPosition = Math.floor(curPosition / 2);
        }
    }

    pop(){
        if(this.arr.length <= 1) return null;
        let curPosition = 1;
        let last = this.arr[curPosition];
        if(2 < this.arr.length) this.arr[curPosition] = this.arr.pop();
        else this.arr.pop();

        while (curPosition * 2 < this.arr.length) {
            if (curPosition * 2 + 1 < this.arr.length && this.arr[curPosition * 2 + 1][0] <= this.arr[curPosition * 2][0] && this.arr[curPosition * 2 + 1][0] < this.arr[curPosition][0]) { //양쪽이 있고 왼쪽이 작을 경우
                let tmp = this.arr[curPosition * 2 + 1];
                this.arr[curPosition * 2 + 1] = this.arr[curPosition];
                this.arr[curPosition] = tmp;
                curPosition = curPosition * 2 + 1;
            } else if (this.arr[curPosition * 2][0] < this.arr[curPosition][0]){
                let tmp = this.arr[curPosition * 2];
                this.arr[curPosition * 2] = this.arr[curPosition];
                this.arr[curPosition] = tmp;
                curPosition = curPosition * 2;
            } else {
                break;
            }
        }

        return last;
    }
}

function solution(land, height) {

    let visited = new Array(land.length).fill(0).map(_ => new Array(land[0].length).fill(0));

    return searchMap(0, 0, visited,land, height);
}


function searchMap(row, col, visited, land, height) {
    const up = [-1,0,1,0];
    const right = [0,-1,0,1];

    let queue = new Array([0, row, col]); //cost, row, col
    let result = 0;
    let priorityQ = new PriorityQ();

    while (queue.length) {
        let [cost, rr, cc] = queue.shift();
        if(visited[rr][cc] == 0) {
            visited[rr][cc] = 1;
            result += cost;

            for (let i = 0; i < 4; i++) {
                let tRr = rr + up[i];
                let tCc = cc + right[i];

                if(tRr < 0 || tCc <0 || land.length <= tRr || land[0].length <= tCc || 0 < visited[tRr][tCc]) continue;

                let diff = Math.abs(land[tRr][tCc] - land[rr][cc]);

                if(diff <= height) queue.push([0, tRr, tCc]);
                else priorityQ.push(diff, [tRr,tCc]);
            }
        }

        if (queue.length == 0) {
            let next = priorityQ.pop();
            if(next != null) queue.push([next[0], ...next[1]]);
        }
    }

    return result;
}
console.log(solution([[1, 4, 8, 10], [5, 5, 5, 5], [10, 10, 10, 10], [10, 10, 10, 20]], 3));
console.log(solution([[10, 11, 10, 11], [2, 21, 20, 10], [1, 20, 21, 11], [2, 1, 2, 1]], 1));

 

- union find로 cost가 낮은 Parent를 유지 하는 방법도 좋은거 같다. 시간날때 도전해 봐야겠다.