[프로그래머스/Python] 등산코스 정하기 (2022 KAKAO TECH INTERNSHIP)

📌문제 탐색하기

• XX산은 n개의 지점으로 이루어져 있고, 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 봉우리
• 각 지점은 양방향 통행이 가능하며 이동하는데 일정 시간이 소요되는 등산로로 연결되어 있음
• 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현
• 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있음
• 휴식 없이 이동해야 하는 시간 중 가장 긴 시간 = 해당 등산코스의 intensity
• XX산의 출입구 중 한 곳에서 출발하여 산봉오리 중 한 곳만 방문한 뒤 다시 원래 출입구로 돌아오는 등산코스를 정하려고 함
  • 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함
• intensity가 최소가 되도록 등산코스 정하기

매개 변수

• 지점의 개수 n, 출입구 지점 배열 gates, 산봉우리 지점 배열 summits 

제한 사항

• 2 ≤ n ≤ 50,000
• n-1 ≤ paths의 길이 ≤ 200,000
• paths의 원소: [i, j, w]의 형태 (i, j번 지점을 연결하고, 이동하는 데 w만큼 소요되는 등산로가 있음)
  • 1 ≤ i < j ≤ n
  • 1 ≤ w ≤ 10,000,000
  • 서로 다른 두 지점을 직접 연결하는 등산로는 최대 1개
• 1 ≤ gates의 길이 ≤ n
  • 1 ≤ gates의 원소 ≤ n
  • gates의 원소는 해당 지점이 출입구임을 나타냄
• 1 ≤ summits의 길이 ≤ n
  • 1 ≤ summits의 원소 ≤ n
  • summits의 원소는 해당 지점이 산봉우리임을 나타냄
• 출입구이면서 산봉우리인 지점 없음
• gates와 summits에 등장하지 않은 지점은 모두 쉼터
• 임의의 두 지점 사이에 이동 가능한 경로가 항상 존재함

반환 값

• 배열 [산봉우리의 번호, intensity의 최솟값]
  • intensity가 최소가 되는 등산 코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스 선택하기

풀이 방법 생각해보기

우선 산봉우리에 도착만하면, 왔던 경로 그대로 되돌아오는 것은 상관없으므로 출입구에서 산봉우리까지 가는 것만 고려하면 된다. 각 출입구에서 출발해서 다른 출입구를 거치지 않도록 하면서, 다익스트라 방식으로 다른 노드까지의 최 intensity를 갱신해 나가며 탐색하면 결국 모든 노드까지의 intensity를 구할 수 있다. 이를 토대로 산봉우리까지의 가장 최소 intensity와 그 산봉우리의 번호를 구하면 된다.

 

📌코드 설계하기

1. 등산로 정보를 저장할 인접 리스트 graph를 생성하고, paths 리스트를 토대로 정보를 추가한다.
2. i번째 지점이 출입구 혹은 게이트인지 쉽게 알게 하기 위해 is_gate, is_summit 리스트를 생성해 모든 요소를 False로 초기화하고, gates와 summits을 토대로 해당 지점만 True로 바꿔준다.
3. 각 지점까지의 현재 최소 intensity를 관리할 리스트 intensity를 생성하고 모든 요소를 무한대로 초기화한다.
4. 각 탐색 단계에서 intensity가 가장 낮은 노드를 빠르게 선택하기 위해 우선순위큐 hq를 생성한다.
5. gates를 토대로 각 출입구의 intensity를 0으로 초기화하고, hq에 (0, 출입구 번호)를 heappush한다.
6. hq가 빌 때까지 아래 과정을 반복한다.
   1. hq에서 heappop을 통해 (현재 intensity, 현재 노드)를 꺼낸다.
   2. 만약 현재 intensity 값이 intenisity 리스트에 기록된 현재 노드까지의 최소 intensity 값보다 크다면 탐색할 필요가 없으므로 continue.
   3. 만약 현재 노드가 summit이라면 더 경로를 이어갈 필요가 없으므로 continue
   4. graph를 통해 현재 노드의 이웃 노드를 방문하면서, 현재 intensity 값와 다음 노드까지 가는데 걸리는 시간 중 더 큰 값을 새로운 intensity 값으로 설정한다. 다음 노드가 출입구가 아니고, 새로운 intensity 값이 intensity 리스트에 기록된 다음 노드까지의 최소 intensity 값보다 작다면 hq에 (새로운 intensity, 다음 노드)를 heappush한다.
7. summits로 받은 모든 산봉우리를 번호가 낮은 순서대로 돌면서, 가장 intensity가 낮은 산봉우리를 찾는다.
8. 7에서 찾은 산봉우리 번호와 해당 산봉우리까지의 intensity를 리스트 형태로 반환한다. 

 

📌시도회차 수정사항

1회차

위 코드 설계하기 과정의 4~6번 과정을 함수로 만들어 출입구들마다 해당 함수를 호출해서 각 출입구에서 출발했을 때 최소 intenstity를 찾고자 했다. 그 과정에서 이미 최소 intensity를 찾았음에도 중복으로 탐색하는 경우가 발생해서 일부 테스트케이스에서 시간초과를 받았다.

출입구마다 탐색 과정을 반복하는 것이 아니라, 한 번의 다익스트라 실행으로 모든 경로를 탐색하도록 수정했다.

 

📌정답 코드

from collections import deque
from heapq import heappush, heappop

def solution(n, paths, gates, summits):
    INF = int(1e8)
    
    graph = [[] for _ in range(n+1)]
    for i, j, w in paths:
        graph[i].append((j, w))
        graph[j].append((i, w))
    
    is_gate = [False]*(n+1)
    is_summit = [False]*(n+1)
    for g in gates:
        is_gate[g] = True
    for s in summits:
        is_summit[s] = True
        
    intensity = [INF]*(n+1)
    hq = []
    for g in gates:
        intensity[g] = 0
        heappush(hq, (0, g))
    
    while hq:
        cur_intensity, cur_node = heappop(hq)

        if cur_intensity > intensity[cur_node]:
            continue

        if is_summit[cur_node]:
            continue

        for next_node, next_intensity in graph[cur_node]:
            next_intensity = max(cur_intensity, next_intensity)
            if not is_gate[next_node] and next_intensity < intensity[next_node]:
                intensity[next_node] = next_intensity
                heappush(hq, (next_intensity, next_node))
    
    summits.sort()
    answer = [0, INF]
    
    for s in summits:
        if intensity[s] < answer[1]:
            answer = [s, intensity[s]]
    
    return answer