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

등산코스 정하기

import collections

def makeGraph(paths, n):
    result = collections.defaultdict(list)
    for g1, g2, way in paths:
        result[g1].append([g2, way])
        result[g2].append([g1, way])
    return result

def bfs(n, graph, gates, summits, distance):
    que = collections.deque(gates)
    while que:
        cur_loc = que.popleft()
        if cur_loc in summits: continue
        for next_loc, way in graph[cur_loc]:
            if distance[next_loc] > max(distance[cur_loc], way):
                que.append(next_loc)
                distance[next_loc] = max(distance[cur_loc], way)
                
    return distance
        
def solution(n, paths, gates, summits):
    answer = []
    graph = makeGraph(paths, n)
    summits_dict = {}
    min_dis = float('inf')
    min_summit = -1
    for summit in summits:
        summits_dict[summit] = 1
    
    distance = [10000001 for _ in range(n+1)]
    for gate in gates:
        distance[gate] = 0
        
    distance = bfs(n, graph, gates, summits_dict, distance)
        
    for summit in summits:
        if min_dis > distance[summit]:
            min_dis = distance[summit]
            min_summit = summit
        elif min_dis == distance[summit] and min_summit > summit:
            min_summit = summit
                
    return [min_summit, min_dis]

이 글을 보시는 분들은 문제는 다 아실거라 생각하고 바로 문제 해설로 들어 가겠습니다.

문제해설

일단 BFS를 이용하여 문제를 해결하였습니다.

1. que에 출발지를 모두 넣어 놓습니다.

2. BFS를 통해 갈 수 있는 모든 길을 탐색합니다.

   길을 탐색하는 조건은 이전에 저장된 길 보다 지금 가려는 길이 짧은 경우만 다음 길을 갑니다.

3. 그리고 정상에 도착했을때는 다음 길을 개척하지 않습니다.

4. 이런 식으로 BFS를 통해 게이트부터 정상까지 갈 수 있는 짧은 길을 distance에 정한 후 문제에서 요구하는 대로 정답을 도출하여 리턴하면 됩니다.