[프로그래머스] 등산코스 정하기

등산코스 정하기

프로그래머스

 

• 첫 풀이 - 시간초과 fail
  • dfs + 메모이제이션 

from collections import deque, defaultdict
import sys
sys.setrecursionlimit(10**6)

def solution(n, paths, gates, summits):
    graph=defaultdict(list)    
    dp=[float('inf') for _ in range(n+1)]
    tmp=float('inf')
    answer=float('inf')
    
    for path in paths:
        s,e,d=path
        graph[s].append((e,d))
        graph[e].append((s,d))

    def dfs(cur, d):
        nonlocal tmp,answer
        
        if tmp<d:
            return
        if cur in summits:
            if tmp<d:
                return
            if tmp==d and answer<cur:
                return
            answer=cur
            tmp=dp[cur]
            return
        
        for nxt_set in graph[cur]:
            nxt, nxt_d= nxt_set
            if nxt in gates:
                continue
            
            if dp[nxt]<=max(d,nxt_d):
                continue
                
            dp[nxt]=max(d,nxt_d)
            dfs(nxt, dp[nxt])
    
    for gate in gates:
        dp[gate]=0
        dfs(gate,0)

    return [answer,tmp]

 

• 두번째 풀이 - bfs + 다익스트라
  • 이 문제 좀 이상한듯;;
  • in 사용하는데 set으로 안바꾸면 시간초과남;;
  • 산봉우리일 때 값 비교해서 바로 바꿔줘야 시간 더 단축됨

from collections import defaultdict
import heapq

def solution(n, paths, gates, summits):
    graph = defaultdict(list)
    gates = set(gates)
    summits = set(summits)

    for s, e, d in paths:
        graph[s].append((e, d))
        graph[e].append((s, d))

    dp = [float('inf')] * (n + 1)
    tmp = float('inf')
    answer = -1

    def bfs(gate):
        nonlocal tmp, answer
        queue = [(0, gate)]
        dp[gate] = 0

        while queue:
            cur_d, cur = heapq.heappop(queue)

            if cur_d > dp[cur]:
                continue

            if cur in summits:
                if tmp < cur_d:
                    continue
                if tmp == cur_d and answer < cur:
                    continue
                answer = cur
                tmp = cur_d
                continue

            for nxt, nxt_d in graph[cur]:
                if nxt in gates:
                    continue

                new_d = max(cur_d, nxt_d)
                if new_d < dp[nxt]:
                    dp[nxt] = new_d
                    heapq.heappush(queue, (new_d, nxt))

    for gate in gates:
        bfs(gate)

    return [answer, tmp]