23.04.24 파이썬 코딩 퀴즈#234 등산코스 정하기 (프로그래머스 스쿨)

이번 문제는 등산코스 정하기 문제이다.

그동안 밀렸던 level 0 문제들을 일부 풀고, 다시 level 3으로 넘어왔다.

먼저 문제 설명을 읽어보자

XX산은 n 개의 지점으로 이루어져 있으며, 각 지점은 1부터 n 까지 번호가 붙여져 있다. 이 때 각 지점은 양방향 통행이 가능한 등산로로 연결되어 있으며, 등산로별로는 이동하는데 일정 시간이 소요된다.

등산코드는 방문할 지점 번호들을 순서대로 나열하여 표현 가능하며, 1-2-3-2-1 은 1번 지점에서 출발하여 2번,3번,2번,1번 지점을 순서대로 방문한다는 의미이다.

이때, 휴식없이 이동 해야 하는 시간 중 가장 긴 시간을 해당 등산코스의 intensity 라고 부르기로 하며, 당신은 이 intensity 가 최소가 되도록 하는 등산코스를 정해야 한다.

위 그림은 입출력 예 1번을 그림으로 표현한 모습이다.

1번과 3번이 출발 게이트가 되며, 5번은 봉우리가 된다.

만약 1-2-5-2-1 순서로 방문하게 되면, intensity는 4가 된다. (해당 등산코스의 가장 긴 시간이 intensity 이다.)

만약 1-2-4-5-6-4-2-1 로 방문하게 되면, intensity 는 3이 된다.

3을 시작점으로 놓고보면 2와 4번으로 이동 가능한데, 이때 각 intensity 는 최소 5, 4 가 된다.

따라서 가장 낮은 intensity 로 방문 가능한 코스는 5번 봉우리를 방문하는 최소 intensity 3 이다.

 

만약, 전달받은 봉우리가 여러개이고, 각 intensity 가 동일하다면, 가장 낮은 번호의 봉우리 번호를 반환해야 한다.

특별한 제한 사항은 없다.

입출력 예 2번을 살펴보자.

1번에서 2번,3번,4번 봉우리로 가는 등산코스는 

[1-6-5-2-5-6-1], [1-7-3-7-1], [1-4-1] 총 3개의 코스이며 각 intensity 는 6, 4, 4 이다.

따라서 번호가 낮은 3번 봉우리를 방문하는 [3,4]를 return 하면 된다.

다음은 입출력 3번 이다.

시작 위치는 3번과 7번이며, 두개의 봉우리 1번과 5번이 있다.

만약 7-6-5-4-1-4-5-6-7 로 등산코스를 짜면 5번 봉우리를 두번 방문하기 때문에 올바르지 않은 등산 코스가 된다.

따라서 해당 문제는 7번에서 시작해서 5번 봉우리를 방문하는 intensity 1 을 배열에 담아 return 하면 된다. [5,1]

다음은 입출력 예 4번 문제이다.

출발지는 1번 2번 이고 봉우리는 5번 하나이다. 이 경우 최소 intensity 는 6이다. [5,6]

바로 코드로 작성해 보았다.

첫번째 코드는 언제나 처럼 방문 처리를 통한 전체 탐색이다.

연결된 지점들을 순서대로 방문하고, 다시 돌아오는 코스가 아닌 봉우리 까지만 방문 후 intensity 를 확인하고 갱신하는 방법이다.

정확하게 13문제에서 시간초과에 걸린다.... 

 

다시 작성한 코드. 오랜만에 heapq 가 등장했다.

heapq를 제대로 사용하기 위해 heap에 저장되는 자료구조는 (intensity, 번호) 로 바꾸어 주었다.

그리고 이번에는 방문 형태가 아닌, 현재 방문 지점의 최소값을 저장하는 형태로 바꾸었다.

먼저 gates를 돌면서 (0, gate) 를 heap 에 넣어주고 시작한다.

그 다음 heap 에서 하나씩 가져와서 intensity 위주로 값을 확인해야 한다.

1. 현재 등산루트의 intensity 가 기존에 저장된 값보다 크다면, 해당 루트를 확인할 필요가 없다

2. 만약 봉우리에 도달한 경우라면 더 이상 진행할 필요가 없다

3. 이동 가능한 위치를 탐색할때에는, 현재 intensity 와 다음 진행 intensity 중 높은 값을 선택해서 저장하고, 해당 값이 기존에 진행했던 값(info_intensity[next]) 보다 적은 경우에만 값을 갱신하고 heap에 해당 경로를 넣어준다.

4. 최종적으로 완성된 info_intensity 를  summits를 확인하고, 그 중 최소값만을 확인하여 answer을 갱신한다.

 

시간초과 문제들 덕분에 상당히 시간을 많이 허비했다.

왜 처음부터 각 지점을 방문하는 최소값을 생각하지 못했는지 참...

좀더 공부가 필요하다.