프로그래머스 등산 코스 정하기 javascript , python

프로그래머스

예제 1

파란색 정점이 입구,

빨간색 정점이 산봉우리,

검은색 정점은 쉼터이다.

 

각 정점사이의 간선은 걷는 시간을 의미한다.

 

입구에서 산봉우리까지 갔다가 다시 돌아올 때 

해당 루트가 지나간 간선들의 최대값이 가장 작은 루트를- 구하여라.

 

루트는 여러가지가 있다. 

 

1 => 2 => 4 => 5 => 4 => 2 => 1

// 각 사이의 간선은 [3, 2, 3, 3, 2, 3] 

// 간선들의 최대 값은 3

 

1 => 2 => 4 => 6 => 5 => 4 => 2 => 1 

// 각 사이의 간선은 [3, 2, 1, 1, 3, 2, 3]

// 간선들의 최대 값은 3

 

 

예제 3번

예제 3 같은 경우 

예제 3 답 [5,1] 이다.

 

그러나

 

정점 1 => 4 => 5

정점 5 => 4 => 1

두 방향으로 가는 경우가 생길 수 있는데 

 

위의 경우가 허용된다면 [1,1], [5,1] 두개가 답이 될 수 있기에 [1,1]이 답이 된다.

그러므로 산봉우리 1, 5 에서 나가는 간선을 제거해 주어야 한다.

 

function solution(n, paths, gates, summits) {
 	// 정점 간선 그래프 만들기
    const graph = new Array(n+1).fill(null).map(_=>[]);
    for(let i = 0 ; i < paths.length ; i++){
        const [a,b,w] = paths[i];
        graph[a].push([w,b]);
        graph[b].push([w,a]);
    }
    
    // 산봉우리에서 나가는 간선 제거
    for(let summit of summits){
        graph[summit] = [];
    }
    
    // 시작 큐
    let q = gates;
    
    // intensity 저장 배열
    const dp = new Array(n+1).fill(Infinity);
    
    // 시작 위치 마이너스 값으로 초기화
    gates.forEach(v=>dp[v] = -1);
 
 	// bfs 변형
    while(q.length > 0){
        let set = new Set();
        while(q.length > 0){
            const qv = q.pop();
            for(let [w,v] of graph[qv]){
                const maxV = Math.max(dp[qv],w);
                if(dp[v] > maxV){
                    dp[v] = maxV;
                    set.add(v);
                }
            }
        }
        q = [...set];
    }
	
    // 정렬해서 배열의 첫번 째 값 가져오기
    const res = summits.map(v=>[v,dp[v]]).sort((a,b)=>{
        if(a[1] === b[1]){
            return a[0] - b[0];
        }
        return a[1]-b[1];
    })
    return res[0];
}

 

아래는 파이썬 다익스트라로 푼 경우이다.

import heapq

def solution(n, paths, gates, summits):
    answer = []
    graph = [[] for i in range(n+1)]
    for a,b,w in paths:
        graph[b].append([w,a])
        graph[a].append([w,b])
        
    for summit in summits:
        graph[summit] = []
        
    def dijkstra():
        summitsSet = set(summits)
        dp = [float('inf') for i in range(n+1)]
        for gate in gates:
            dp[gate] = 0
            
        hq = [[0,gate] for gate in gates]
        heapq.heapify(hq)
        while(hq):
            hqW,hqV = heapq.heappop(hq)
            
            if hqV in summitsSet or hqW > dp[hqV]:
                continue
            
            for [gW,gV] in graph[hqV]:
                m = max(gW,dp[hqV])
                if(dp[gV] > m):
                    dp[gV] = m
                    heapq.heappush(hq,[m,gV])

        return dp
    dp = dijkstra()
    summits.sort(key=lambda x : (dp[x],x))
    return [summits[0],dp[summits[0]]]