여행경로

프로그래머스: 여행 경로 (파이썬, DFS, 백트래킹)

꽤나 어려운 문제였다. 코드를 짜는 것 자체는 어렵지 않았으나 문제의 엣지케이스를 생각하는데 어려움이 있어 처음에 접근을 잘못한 문제다. 주어진 항공권을 모두 써야 하므로 DFS로 접근을 해야함을 알 수 있다. 이때 가능한 경로가 여러 개일수도 있는데 나는 tickets배열을 lambda식으로 정렬하면 알파벳 순서가 앞서는 경로를 탐색할 것이라 생각했다. 그러나 그렇게 풀면 테스크 케이스1에서 계속 실패했는데 이에 대한 엣지케이스를 생각하는 것이 쉽지 않았다. 특정한 엣지 케이스를 생각하진 못했지만 여러개의 경로를 비교해야 하므로 백트래킹을 이용해 풀어야겠다고 생각했다. 백트래킹은 DFS의 응용으로 분기점에서 다른 경로들또한 탐색하도록 하는 알고리즘이다. 문제에서 여행 경로의 길이는 tickets배열의 ..