[프로그래머스] 118669 - 등산코스 정하기 (Python)

로고를 누르면 문제 페이지로 이동합니다.

---

문제 설명

n개의 지점이 있고, 각 노드는 (1) 출입구 (2) 쉼터 (3) 산봉우리 중 하나입니다.

 

등산코스는 아래와 같이 구성됩니다.

출입구 -> 0개 이상의 쉼터 -> 산봉우리 -> 0개 이상의 쉼터 -> 출입구(처음 출입구와 같은 지점)

산봉우리는 반드시 한 번만 포함되어야 하고, 출입구는 처음과 끝에 방문해야 하므로 반드시 2번만 포함되어야 합니다.

 

각 지점에서 다른 지점으로 이동할 때마다 이동 시간이 있는데, 한 등산코스 내에서 가장 긴 이동 시간을 해당 등산 코스의 intensity 라고 합니다.

 

intensity가 최소가 되는 등산 코스를 구해 [산봉우리의 번호, intensity] 를 반환합니다.

 

예를 들어, 아래 그림과 같이 1,3번이 출입구이고 5번이 산봉우리인 경우 표시해둔 두 가지의 경로로 이동하면 최소 3 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에 등장하지 않은 지점은 모두 쉼터입니다.
• 임의의 두 지점 사이에 이동 가능한 경로가 항상 존재합니다.

풀이

첫 번째 풀이

아이디어

출발지에서 산봉우리까지 도착할 때의 최소 intensity 값을 구하면 똑같은 경로로 출발지로 다시 이동하면 되기 때문에, 편도 경로만을 고려했습니다.

 

다익스트라 알고리즘을 이용하되, 기준값을 경로 내 가중치 합이 아닌 intensity로 두었습니다.

출발지와 도착지가 어디이든 상관없고, 한 지점에 도착하는 intensity 값이 최솟값인 경우가 가장 최선이라 생각했기 때문에 모든 출입구를 우선순위 큐에 넣고 탐색을 시작했습니다.

 

intensity 작은 순, 산봉우리 번호 작은 순 으로 우선순위를 정했기 때문에, 탐색을 하다가 산봉우리를 만난 순간 탐색을 종료했습니다.

코드 (Python)

결과 (Python)

하나의 케이스에서 실패했고, 예외를 찾아보았습니다.

 

첫 번째 풀이

아이디어

그래프가 아래와 같고, 1,2번이 출입구, 3,4번이 산봉우리일 경우, 큐에는 (intensity 1, node 5)와 (intensity 1, node 4)가 삽입되지만, node 4가 먼저 pop되어 node 3은 큐에 삽입되지 못한 채 종료됩니다.

따라서 산봉우리를 만난 순간 종료가 아니라, 탐색이 모두 끝난 뒤 종료합니다.

코드 (Python)

결과 (Python)