[Programmers] 등산 코스 정하기 - swift (Level 3)

문제

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

프로그래머스

문제 요약

파란색이 출입구, 빨간색이 산봉우리, 검은색이 쉼터로 총 n개의 지점으로 이루어진 등산로가 있습니다. 등산객은 이 등산로를 오르기 위해서 등산 코스를 정해야 합니다. 이 때, intensity가 최소인 등산 코스를 구하는 문제입니다.

 

intensity는 휴식 없이 이동해야 하는 시간 중 가장 긴 시간입니다. 위 사진에서 3-2-5-4-3과 같이 등산코스를 정했다면 intensity는 3-2 사이의 5시간입니다. 만약 1-2-4-5-6-4-2-1과 같이 정했다면 intensity는 1-2 사이의 3시간입니다. 

풀이

출입구에서 산봉우리까지, 그리고 산봉우리에서 출입구까지 등산코스의 intensity는 왔던 길을 되돌아가면 되므로 같습니다. 따라서 출입구에서 산봉우리까지의 경우만 생각할 수 있습니다.

 

출입구에서 산봉우리까지 가는데 최소의 intensity를 구하기 위해서는 다익스트라 알고리즘을 사용할 수 있습니다. 일반적인 다익스트라 알고리즘은 출발 지점에서 모든 지점까지의 최소 거리를 구합니다. 이 문제에선 다익스트라 알고리즘을 약간 변형하여 distance 배열이 아닌, intensity 배열을 둡니다. 즉, 출입구에서 출발하여 각 n번째 지점까지 갈 때까지 최소 intensity 배열을 두어 다익스트라 알고리즘을 돌릴 수 있습니다. 

 

출입구가 여러개여도 상관없습니다. 시작 지점을 여러개로 설정하여 시작하는 것일 뿐입니다. 알고리즘을 돌다가 최소 intensity가 아닐 경우엔 해당 등산 코스에서 탐색을 멈추기 때문입니다. 

 

첫번째 풀이 코드

⚠️ HEAP 코드는 생략했습니다. 코드가 너무 길어지기 때문에 아래에 전체 코드를 첨부했습니다.

 

 

결과 - 테스트3번 케이스 실패

아래 테스트 3번 케이스를 실패합니다. 

 

 

반례를 생각해보면, 7-6-5-4-1을 통해 산봉우리를 찍고 돌아오는 경우가 생기기 때문에 실패했습니다. 

산봉우리 5번에 도달하면 다시 되돌아가야 한다는 문제 조건이 있습니다. 

 

따라서, 위 코드에서 산봉우리에서 다음 쉼터로 이동하는 케이스를 배제해야합니다. 

 

이 때 주의할 것이 있습니다.

처음에는 paths를 graph로 변환해줄 때, "산봉우리 -> 쉽터"의 경우를 저장하지 않는 방법을 생각했습니다. 하지만 이 방식은 테스트 케이스 17, 18, 23, 24, 25번이 시간 초과가 납니다. 총 n개의 지점이 있고 모두 산봉우리일 수 있기 때문입니다. O(n^2)

따라서, 산봉우리를 자료구조에 저장하여 다익스트라 알고리즘을 돌릴 때, 산봉우리라면 건너뛰도록 구현했습니다. 

 

두번째 풀이 코드

 

⚠️ HEAP 코드는 생략했습니다. 코드가 너무 길어지기 때문에 아래에 전체 코드를 첨부했습니다.

 

 

결과 - 성공

 

세번째 풀이 코드 

더 생각해보면 다익스트라 알고리즘 뿐만 아니라 bfs로도 풀 수 있습니다. intensity 배열을 그대로 사용하여 자료구조가 힙이 아니라 단순 배열이어도 결과는 성공입니다. 힙을 구현하지 않아도 되기에 이 풀이가 더 좋아보입니다. 카카오 풀이를 읽어보면, bfs를 출발점 개수만큼 돌리면 시간 초과가 난다고 합니다만, 아래 코드에선 나지 않았습니다. 만약 시간 초과가 난다면 위와 마찬가지로 출발점을 모두 넣고 bfs를 1번 돌려야 합니다. 시간 초과가 나는 이유는 출발점의 개수가 N개일 수 있기 때문입니다. 시간 복잡도가 N이 곱해집니다.

 

 

힙 코드

 

힙 구현은 아래 링크를 참고 바랍니다.

 

https://github.com/wody-d/woody-iOS-tip/blob/main/TIL_2022:10:10_heap.md

GitHub - wody-d/woody-iOS-tip: 🐶 iOS에 대한 소소한 팁들과 개발하다 마주친 버그 해결기, 그리고 오늘