[코테] 등산코스 정하기

programmers

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

문제 풀이

• 노드 정보
  1 ~ n 까지의 각 노드는 쉼터/출입구/산봉우리 이다.
  출입구와 산봉우리가 아닌 노드(지점)은 쉼터이다.
  따라서, 각 지점이 쉼터인지 아닌지 n(1)로 알기 위해 리스트로 저장해두었다.

    node_info = {i: 0 for i in range(1, n+1)}
        for node in gates:
            node_info[node] = 1
        for node in summits:
            node_info[node] = 2

• output
  출입구에서 산봉우리, 산봉우리에서 출입구로 내려오면서 각 지점으로 이동할 때 cost가 최소여야 한다. 즉, 기존의 다익스트라 문제처럼 최단거리를 갱신하는 방법이 아니라 코스의 최대 intensity를 저장해야 한다.

처음에는 (출입구, 산봉우리) 순서쌍으로 탐색을 했었는데, 시간초과가 났다. 출입구 + 산봉우리 = n이기 때문에 경우의 수가 커질 수 밖에 없다. 따라서 문제를 다시 읽어본 결과, 코스에는 산봉우리 하나만 포함된다는 말이 적혀있었다. 그래서 산봉우리를 기준으로 탐색할 수 있도록 변경했다.

하나의 코스마다 산봉우리는 하나만 포함될 수 있으므로 건너뛰기를 해주었다.

	if dist > distances[now] or node_info[now] == 2:
         continue

그래프를 탐색하면서 출입구인 지점은 제외해주었다. 더 이상 탐색할 필요가 없기 때문이다.

for node, cost in graph[now]:
    if node_info[node] == 1:
        continue
    cost = max(cost, distances[now]) # 최단거리가 아닌, 코스의 최대 intensity를 저장한다.
    if cost < distances[node]:
        distances[node] = cost
        heappush(q, (cost, node))

코드

from heapq import heappop, heappush

def search(start, node_info, graph, distances):
    q = [(0, start)]

    while q:
        dist, now = heappop(q)

        if dist > distances[now] or node_info[now] == 2:
            continue

        for node, cost in graph[now]:
            if node_info[node] == 1:
                continue
            cost = max(cost, distances[now])
            if cost < distances[node]:
                distances[node] = cost
                heappush(q, (cost, node))
                

def solution(n, paths, gates, summits):
    answer = [-1, 10000001]

    node_info = {i: 0 for i in range(1, n+1)}
    for node in gates:
        node_info[node] = 1
    for node in summits:
        node_info[node] = 2

    graph = [[] for _ in range(n + 1)]
    for a, b, c in paths:
        graph[a].append((b, c))
        graph[b].append((a,c))

    distances = [int(1e9) for _ in range(n + 1)]
    for gate in gates:
        distances[gate] = 0
        search(gate, node_info, graph, distances)

    for summit in summits:
        if distances[summit] < answer[1]:
            answer = [summit, distances[summit]]
        elif distances[summit] == answer[1] and answer[0] > summit:
            answer[0] = summit

    return answer