[프로그래머스] 여행경로 (C++)

---

간단한 그래프 선회 문제인 줄 알고 풀다가 주어진 항공권을 모두 사용해야 한다는 제약 조건을 뒤늦게 봐서 풀이 시간이 길어졌다. 무려 첫 번째 문장인 데다가 입출력 예제 #2를 보면 바로 알 수 있는 내용인데 안일했다.

 

그냥 무식하게 아직 사용하지 않은 ticket을 사용해나가면서 그래프를 돌면 된다. 문제 조건에 모든 도시를 방문할 수 없는 경우는 주어지지 않다고 되어 있어서 백트래킹을 따로 고민하기 싫었다. 하지만 그러면 문제가 풀리지 않는다. 따라서 적절한 백트래킹을 추가해주어야 한다. 딱히 크게 고민할 건 없고 경로에서 마지막으로 방문했던 공항을 빼주기면 한다.

 

---

이 문제를 풀면서 가장 헷갈린 부분이 tickets의 최대 크기가 주어지지 않다는 점이였다. 그래서 알고리즘을 설계하는 단계에서 시간 복잡도를 생각하기 어려웠다. 사실 이번 문제에서 사용한 알고리즘은 tickets의 크기가 크다면 적절하지 않은 알고리즘이다. visited 벡터를 그냥 크기가 5000개인 배열로 사용했을 때도 잘 작동하는 것으로 보아 tickets의 최대 크기는 5000 미만인 것으로 보인다. 문제는 맞혔지만 찝찝함이 남는 문제였다. 백준이였다면 이런 점에서는 문제 관리가 참 잘된다는 생각이 들었다.