99클럽 코테 스터디 12일차 TIL - 43164 여행경로

43164. 여행경로 / c++ / level3 / 1시간+

문제 및 코드

접근 방식

그래프 탐색 / BFS / 구현 / 백트래킹

1. 우선 tickets 을 순회 하면서 인접리스트인 adjMap (unordered_map<string,vector>) 을 준비
2. 여행 경로를 담을 vector currentPath를 선언
3. currentPath에 출발지인 ICN을 삽입
4. adjMap에서 ICN을 출발지로 하는 인접리스트를 돌면서 백트래킹 시작
5. currentPath.back (마지막 여행지) 를 출발점으로 하는 인접행렬을 순회하며 다시 백트래킹 반복
6. 백트래킹 도중 currentPath가 ticket + 1 (출발지인 ICN까지 포함하므로) 가 되면, vector 인 answer와 비교하여, 사전순으로 앞서있는지 체크
7. currentPath 가 answer 보다 사전순으로 앞서있다면 answer 갱신

생각해 볼 점

1. 공항의 수가 최대 10’000개였기 때문에 백트래킹 (재귀) 은 과하게 depth가 깊어지면 stack overflow 가 날 수 있다고 걱정했다.
2. 그래서 처음엔 백트래킹을 사용하지 않고 BFS를 써서 어떻게든 풀어보려고 온몸비틀기를 했는데, 출발지 + 도착지를 한 string으로 묶어서 순서를 매겼더니, 중복되는 티켓을 처리하지 못하는 문제가 생겼다.
3. 그래서 밑져야 본전이라고 백트래킹으로 풀어봤더니 너무 잘 풀리고, 시간도 2번에서 풀었던 것보다 1ms 더 빨랐다.
4. 항상 가장 간단한 방법부터 시도해봐야한다고 머리로는 알고 있는데, 시간 제한이 있다고 생각하면 그게 잘 안되는 것 같다.

해시태그

#99클럽 #코딩테스트 준비 #개발자 취업 #항해99 #TIL