[2022 KAKAO TECH INTERNSHIP] Q4. 등산코스 정하기 (C++, Python, Java)

문제 링크

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

 

예상 난이도

G2

 

알고리즘 분류

다익스트라

 

풀이

문제 설명이 조금 난해하긴 하지만 아무튼 결국 출입구에서 산봉우리로 가는 최단 경로를 구하는 문제입니다. 원래는 왕복이지만 그냥 가장 짧은 루트로 올라갔다가 그대로 내려오면 되겠죠. 그리고 이 때 "최단 경로"의 정의가 비용의 합이 아니라 거쳐가는 간선 중 최댓값으로 바뀝니다.

 

그리고 이 경우에도 다익스트라가 잘 적용됩니다. 이건 다익스트라의 정당성을 생각해보면 이해가 가능한데, 다익스트라 알고리즘이 잘 동작했던 이유는 매 순간마다 가장 가까운 정점을 찾으면 그 정점까지의 거리를 확정할 수 있었기 때문입니다. 그리고 이 논리는 최단 경로의 정의가 거쳐가는 간선 중 최댓값으로 바뀐 후에도 잘 동작합니다.

 

그래서 다익스트라에서 거리를 갱신하는 로직을 변경하고 출입구가 여러 개이기 때문에 여러 개의 시작점을 가지는 다익스트라를 돌리면 됩니다. 또 산봉우리를 한 번만 방문해야 한다는 조건을 고려하지 않으면 당장 예제 3번에서 반례가 나오게 되는데, 이 조건을 만족시키기 위해 산봉우리에 도달하면 해당 정점을 우선순위 큐에 넣지 않아 해당 정점을 타고 다른 산봉우리로 가지 못하게끔 합니다. 저는 이렇게 우선순위 큐에 넣지 않는 방법을 사용했지만 공식 풀이 블로그에서는 간선을 단방향으로 두는 방법을 제시하고 있습니다.

 

다익스트라 이외에도 Parametric Search+BFS, Union Find 등 다양한 해결 방법이 있고 저는 사실 처음 풀 당시에 최단 경로의 정의를 바꾼 다익스트라를 떠올리지 못해 Parametric Search+BFS로 접근했었습니다.

 

코드(C++)

 

코드(Python)

 

코드(Java)