https://school.programmers.co.kr/learn/courses/30/lessons/118669
input :
- 2 ≤ n ≤ 50,000
- n - 1 ≤ paths의 길이 ≤ 200,000
- paths의 원소 : [i, j, w] 형태
- 1 ≤ gates의 길이 ≤ n
- 1 ≤ summits의 길이 ≤ n
output :
- intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최솟값을 차례대로 정수 배열에 담아 return
조건 :
- 등산코스의 intensity : 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간intensity
- 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스
idea
애매했던 부분은 BFS, DFS로 충분할까 였다. visit을 어떻게 표현할 것이며 시간 복잡도가 될지가 애매했다.
2022.12.28
틀린 부분
- summits의 배열 원소가 정렬이 되지 않을 수도 있다.
- 모든 gate들을 따로 해서 산봉우리까지를 찾으려 했다.
해당 출입구를 구분할 필요가 없다. 쉼터나 산봉우리까지 갈 떄 우리가 필요한건 최대의 intensity일 뿐이기에 해당 지점까지의 최대 값만 저장하면 된다. 출발지가 필요없다.
해설
해설
출입구에서 이동을 하면서 산봉우리까지의 최대 intensity가 최소인 값을 찾는 것이었다.
요구한 정답을 따르면 (산봉우리, 최대 intensity)일 뿐 출발지는 필요가 없다.
걍 특정 지점에서 산봉우리 까지의 intensity만 구하면 되는 것이다.
물론 생각은 비슷했는데 정확한 공식을 만들어 내지 못했다.
이를 통해 구현을 하는데 몇 가지 따져야 할 부분이 있었다.
주의
1. 다음 노드가 산 봉우리인 경우엔 반복문을 중단하기.
2. 마지막 정답 구할 시에 오름차순 유지하기.
from collections import deque
def solution(n, paths, gates, summits):
summits.sort()
dict_sum = dict()
dist, graph = [float("inf")] * (n + 1), [[] for _ in range(n + 1)]
for item in summits:
dict_sum[item] = 1
for i, j, w in paths:
graph[i].append((j, w))
graph[j].append((i, w))
q = deque([])
for item in gates:
q.append(item)
dist[item] = 0
while q:
node = q.popleft()
if node in dict_sum:
continue
for next_node, wei in graph[node]:
temp_wei = max(dist[node], wei)
if dist[next_node] <= temp_wei:
continue
dist[next_node] = temp_wei
q.append(next_node)
no, value = -1, float("inf")
for item in summits:
if value > dist[item]:
no, value = item, dist[item]
return [no, value]