[프로그래머스 Lv3] 파이썬 - 등산 코스 정하기

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

# 조건

• XX산은 n개의 지점으로 이루어져 있습니다.

• 각 지점은 1부터 n까지 번호가 붙어있으며, 출입구, 쉼터, 혹은 산봉우리입니다.

• 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 서로 다른 지점을 이동할 때 이 등산로를 이용해야 합니다.

  • 이때, 등산로별로 이동하는데 일정 시간이 소요됩니다.

• 등산코스는 방문할 지점 번호들을 순서대로 나열하여 표현할 수 있습니다.

  • 예를 들어 1-2-3-2-1 으로 표현하는 등산코스는 1번지점에서 출발하여 2번, 3번, 2번, 1번 지점을 순서대로 방문한다는 뜻입니다.

• 등산코스를 따라 이동하는 중 쉼터 혹은 산봉우리를 방문할 때마다 휴식을 취할 수 있으며, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity라고 부르기로 합니다.

• 당신은 XX산의 출입구 중 한 곳에서 출발하여 산봉우리 중 한 곳만 방문한 뒤 다시 원래의 출입구로 돌아오는 등산코스를 정하려고 합니다.

  • 다시 말해, 등산코스에서 출입구는 처음과 끝에 한 번씩, 산봉우리는 한 번만 포함되어야 합니다.

• 당신은 이러한 규칙을 지키면서 intensity가 최소가 되도록 등산코스를 정하려고 합니다.

• 다음은 XX산의 지점과 등산로를 그림으로 표현한 예시입니다.
  

• 위 그림에서 원에 적힌 숫자는 지점의 번호를 나타내며, 1, 3번 지점에 출입구, 5번 지점에 산봉우리가 있습니다.

• 각 선분은 등산로를 나타내며, 각 선분에 적힌 수는 이동 시간을 나타냅니다.

  • 예를 들어 1번 지점에서 2번 지점으로 이동할 때는 3시간이 소요됩니다.

• 위의 예시에서 1-2-5-4-3 과 같은 등산코스는 처음 출발한 원래의 출입구로 돌아오지 않기 때문에 잘못된 등산코스입니다.

• 또한 1-2-5-6-4-3-2-1 과 같은 등산코스는 코스의 처음과 끝 외에 3번 출입구를 방문하기 때문에 잘못된 등산코스입니다.

• 등산코스를 3-2-5-4-3 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.

• 이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 5시간입니다. 따라서 이 등산코스의 intensity는 5입니다.
• 등산코스를 1-2-4-5-6-4-2-1 과 같이 정했을 때의 이동경로를 그림으로 나타내면 아래와 같습니다.

• 이때, 휴식 없이 이동해야 하는 시간 중 가장 긴 시간은 3시간입니다.
• 따라서 이 등산코스의 intensity는 3이며, 이 보다 intensity가 낮은 등산코스는 없습니다.
• XX산의 지점 수 n, 각 등산로의 정보를 담은 2차원 정수 배열 paths, 출입구들의 번호가 담긴 정수 배열 gates, 산봉우리들의 번호가 담긴 정수 배열 summits가 매개변수로 주어집니다.
• 이때, intensity가 최소가 되는 등산코스에 포함된 산봉우리 번호와 intensity의 최솟값을 차례대로 정수 배열에 담아 return 하도록 solution 함수를 완성해주세요.
• intensity가 최소가 되는 등산코스가 여러 개라면 그중 산봉우리의 번호가 가장 낮은 등산코스를 선택합니다.

---

제한사항

• 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에 등장하지 않은 지점은 모두 쉼터입니다.
• 임의의 두 지점 사이에 이동 가능한 경로가 항상 존재합니다.
• return 하는 배열은 [산봉우리의 번호, intensity의 최솟값] 순서여야 합니다.

# 접근 방법

• 문제 설명이 길어 조금 이해하기 힘들었다.
• 중요한 점은 => 출발지에서 산봉우리 하나를 거친 후 출발지로 돌아오는 것
  • 이 경로에서 다른 출입구를 지날 수 없다는 점이다.
  • 또한, 산봉우리에 도달하기만 하면 되므로 편도로 생각해주어도 된다.
• 다익스트라를 이용하여 풀어준다.
  • heapq를 이용하여 그 때 그 때 간선이 최소인 경우부터 탐색해준다.
  • bfs를 돌리며 산봉우리를 최초로 만나는 경우 answer에 담아주고 return 해주면 된다.
  • 또한, 출발점이거나 현재 노드를 방문하는 최소의 intensity보다 현재 intent가 크다면 continue를 해준다.
• answer를 x[1], x[0]로 정렬해주며 0번째를 return 해주면 된다.

시간 초과

• 7개의 case에서 시간초과가 발생하였다.
• 모든 gates를 돌면서 체크해주는 것이 아닌 모든 출발지를 q에 넣어준 후 다익스트라를 한 번만 실행해주도록 하였다.

from heapq import heappush, heappop


def solution(n, paths, gates, summits):
    answer = []
    info = [[] for _ in range(n + 1)]
    for i, j, w in paths:
        heappush(info[i], (w, j))
        heappush(info[j], (w, i))

    def bfs(s):
        visited = [float('inf')] * (n + 1)
        q = [(0, s)]
        visited[s] = 0
        while q:
            inten, now = heappop(q)
            if now in summits:
                answer.append([now, inten])
                continue

            for val, next_node in info[now]:
                # 출발점이거나 방문했는데 현재 저장된 intensity보다 크다면 continue
                if next_node in gates or inten > visited[next_node]:
                    continue

                if val < visited[next_node]:
                    visited[next_node] = val
                    heappush(q, (max(inten, val), next_node))

    for i in gates:
        bfs(i)

    answer.sort(key=lambda x: (x[1], x[0]))

    return answer[0]

• 변경한 부분
  • 시간 초과가 3개로 줄었다.

 def bfs():
        visited = [float('inf')] * (n + 1)
        q = []
        for i in gates:
            q.append((0, i))
            visited[i] = 0

pass 코드

• 비교해주는 부분을 for문에서가 아닌 heapq에서 뽑았을 때 해주었다.
  • 현재 노드에 기록된 값이 intensity보다 작다면 continue를 해주었고
  • for 문 안에서는 다음 노드로 가는 값과, 현재 inten 중에 큰 값이 visited[다음 노드]보다 작다면 추가해주었다.

from heapq import heappush, heappop


def solution(n, paths, gates, summits):
    global answer
    answer = [50001, 10000000]
    info = [[] for _ in range(n + 1)]
    for i, j, w in paths:
        heappush(info[i], (w, j))
        heappush(info[j], (w, i))


    visited = [float('inf')] * (n + 1)
    q = []
    for i in gates:
        q.append((0, i))
        visited[i] = 0
    while q:
        inten, now = heappop(q)
        if visited[now] < inten:
            continue
        if now in summits:
            if inten <= answer[1]:
                if inten < answer[1]:
                    answer = [now, inten]
                elif inten == answer[1] and now < answer[0]:
                    answer = [now, inten]
            continue

        for val, next_node in info[now]:
            if max(val,inten) < visited[next_node]:
                visited[next_node] = max(inten, val)
                heappush(q, (max(inten, val), next_node))

    return answer