등산코스 정하기

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

문제 파악 [필수 작성]

문제이해

출입구-산봉우리-출입구 순으로 만들 수 있는 길 중
경로상 가중치가 가장 작은 길을 찾아야됨

제한 조건 확인

노드는 최대 5만개
엣지는 최대 20만개
노드번호는 1번부터 5만까지
가중치는 최대 1천만
두지점을 잇는 엣지는 유일
출입구이면서 산봉우리인 경우는 없음

아이디어

방문하지 않은 것 중 intensity 가 가장 낮은 순으로 확장해 나가야함
확장 도중 산봉우리가 발견되면
해당 산봉우리와 현재까지의 intensity 중 최대값을 리턴하고 종료
다시 산봉우리부터 출입구까지
만약 intensity 가 같은 등산코스가 여러개면
해당 intensity 내에 도달할 수 있는 산봉우리 중 가장 낮은 번호를 리턴

힙에 넣는 구조는 (다음노드로의 엣지가중치, 다음노드) 형태
맨 처음 힙에 순서대로 출입구에 연결된 (다음노드로의 엣지가중치, 다음노드) 를 힙에 추가
힙에서 최소값부터 뽑아내면서 영역확장
이때 가중치를 max_heap 에 저장
만약 다음노드번호가 산봉우리 set 안에 있으면
산봉우리 heap 에 해당 산봉우리 노드번호를 추가
현재 max_heap의 강도를 look up 하고
min_heap 에 더이상 없을때까지 pop
pop 한게 해당 강도 내에 갈 수있는거면 확장하고 없는거면 패스

최종적으로, 산봉우리 heap에서 최소값(head), intesity 최댓값(head) 를 리턴

시간복잡도

일반적인 다익스트라 알고리즘 시간과 동일

그 외 paths 순회나 gates 순회나 heap 삽입삭제는 다익스트라 순회에 의해 dominate 됨

(E+V)log(V) = 250,000 log (50,000) < 250,000 log (2^16) = 4,000,000 = 400만 >> 간당하게 통과 예상

시간복잡도를 문제 전에 계산한게 아니라 문제를 다 풀고 코드를 보고 계산한게 조금 아쉬움.

자료구조

접근 방법 [필수 작성]

아이디어

코드 구현 [필수 작성]

1차시도 (35분 소요)

산봉우리를 경로상에 두개씩 포함하는 경우에 대해서 처리를 못함
테스트케이스3번을 틀림
7 6 5 4 1 4 5 6 7 로 인식함
테케에서 걸렸기 때문에 제출 전에 알아차림

그래서 각경로 갈때마다 산봉우리 갯수 저장해주기로함 산봉우리 갯수 2개되면 그냥 pass하게 바꿈

import heapq
import sys

def solution(n, paths, gates, summits):
    INF = sys.maxsize
    min_heap = []
    summit_heap = []
    intensity_heap = []
    visited = [False for _ in range(n+1)]
    summits_set = set(summits)
    link_list = [[] for _ in range(n+1)] #1번노드부터 n번노드까지/0번째 노드는 사용하지 않음
    
    for path in paths:
        link_list[path[0]].append((path[2],path[1]))
        link_list[path[1]].append((path[2],path[0]))
    
    for gate in gates:
        for pair in link_list[gate]:
            visited[gate] = True
            heapq.heappush(min_heap,pair)
            
    max_intensity = INF
    
    while min_heap:
        tmp_intensity, nn = heapq.heappop(min_heap)
        if tmp_intensity <= max_intensity:
            if visited[nn] == False:
                visited[nn] = True
                heapq.heappush(intensity_heap,tmp_intensity*(-1))
                if nn in summits_set:
                    heapq.heappush(summit_heap,nn)
                    max_intensity = intensity_heap[0]*(-1)
                for pair in link_list[nn]:
                    heapq.heappush(min_heap,pair)
    
    return [summit_heap[0],intensity_heap[0]*(-1)]

2차 시도 (코드추가 10분 소요)

import heapq
import sys

def solution(n, paths, gates, summits):
    INF = sys.maxsize
    min_heap = []
    summit_heap = []
    intensity_heap = []
    visited = [False for _ in range(n+1)]
    summits_set = set(summits)
    link_list = [[] for _ in range(n+1)]
    
    for path in paths:
        link_list[path[0]].append((path[2],path[1]))
        link_list[path[1]].append((path[2],path[0]))
    
    for gate in gates:
        for edge_w,nn in link_list[gate]:
            visited[gate] = True
            heapq.heappush(min_heap,(edge_w,nn,0))
            
    max_intensity = INF
    
    while min_heap:
        tmp_intensity, nn, summit_count = heapq.heappop(min_heap)
        if tmp_intensity <= max_intensity:
            if visited[nn] == False:
                visited[nn] = True
                heapq.heappush(intensity_heap,tmp_intensity*(-1))
                if nn in summits_set:
                    summit_count += 1
                    if summit_count >= 2:
                        continue
                    heapq.heappush(summit_heap,nn)
                    max_intensity = intensity_heap[0]*(-1)
                for edge_w,rnn in link_list[nn]:
                    heapq.heappush(min_heap,(edge_w,rnn,summit_count))
    
    return [summit_heap[0],intensity_heap[0]*(-1)]

배우게 된 점 [필수 작성]

해설코드

해설코드는 나 코드와 접근방식이 아예 달랐다.

확장을 해나가면서 현재까지 가장 컸었던 edge의 가중치를 노드에 저장해주는 방식이다.

만약 특정노드에 도착했는데 해당 노드에 저장된 경로상 최대 edge 가중치가 도착했을당시 가지고 있는 가중치보다 작다면 pass

또, 특정노드에 도착했는데 해당 노드가 산봉우리라면 pass

즉, 가장 작은 intensity 로 도달할 수 있는 가중치값들이 각각의 노드에 저장되어있고, 최종적으로 모든 summit 에는 도달할 수 있는 가장 작은 가중치값이 저장되어있다.

최종적으로 모든 summit 에 대해서 가장 작은 가중치값을 가진 최소의 summit 값을 찾아낸다.

from collections import defaultdict
from heapq import heappush, heappop

def solution(n, paths, gates, summits):
    summits.sort()
    summit_set = set(summits)

		#✅ 인풋을 본인이 쓰기 편한 구조로 바꾸기 => 무방향 그래프 만들기
    graph = defaultdict(list)
    for i, j, w in paths:
        graph[i].append((w, j))
        graph[j].append((w, i))

    hq = []
		# visited를 초기값 설정할 때, sys.maxsize등의 큰 값을 써도 되지만, 
		# 제약조건에서 주는 값의 범위보다 1큰 수를 써도 된다.
    visited = [10000001] * (n + 1)

		#✅ 모든 출입구를 우선순위큐에 삽입한다.
    for gate in gates:
        heappush(hq, (0, gate))
        visited[gate] = 0

		#✅ intensity를 기준으로 다익스트라를 진행한다.
    while hq:
        intensity, node = heappop(hq)
        if intensity > visited[node] or node in summit_set:
            continue

        for weight, next_node in graph[node]:
            next_intensity = max(weight, intensity)
            if next_intensity < visited[next_node]:
								#✅ 다익스트라 진행 중 각 노드에 도달하는 과정의 최대 intensity값을 저장한다.
                visited[next_node] = next_intensity
                heappush(hq, (next_intensity, next_node))

		#✅ 다익스트라 완료 후 산봉우리들을 순회하며 정답을 찾는다.
    min_intensity = [0, 10000001]
    for summit in summits:
        if min_intensity[1] > visited[summit]:
            min_intensity[0] = summit
            min_intensity[1] = visited[summit]

    return min_intensity

질문 [ 필수 X ]

Q1. 시간복잡도

시간복잡도 계산을 맞게 한지 궁금합니다.

답변

적절한 시간 복잡도 계산입니다. 수고하셨습니다!