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

꽤나 어려운 문제였다. 코드를 짜는 것 자체는 어렵지 않았으나 문제의 엣지케이스를 생각하는데 어려움이 있어 처음에 접근을 잘못한 문제다. 

 

주어진 항공권을 모두 써야 하므로 DFS로 접근을 해야함을 알 수 있다. 이때 가능한 경로가 여러 개일수도 있는데 나는 tickets배열을 lambda식으로 정렬하면 알파벳 순서가 앞서는 경로를 탐색할 것이라 생각했다. 그러나 그렇게 풀면 테스크 케이스1에서 계속 실패했는데 이에 대한 엣지케이스를 생각하는 것이 쉽지 않았다. 

 

특정한 엣지 케이스를 생각하진 못했지만 여러개의 경로를 비교해야 하므로 백트래킹을 이용해 풀어야겠다고 생각했다. 백트래킹은 DFS의 응용으로 분기점에서 다른 경로들또한 탐색하도록 하는 알고리즘이다. 

문제에서 여행 경로의 길이는 tickets배열의 길이보다 1만큼 크다는 것을 알 수 있다. 따라서 백트래킹 시 배열의 길이가 tickets길이+1이 될때 기존 경로와 새로운 경로를 비교하도록 하면 수월하게 풀림을 볼 수 있었다.

 

다음은 내가 푼 코드의 전문이다. 

from copy import deepcopy


def dfs(node, tickets, visited):
    global cash
    global answer
    # 여행 경로의 길이는 tickets 길이에 1을 더한 값
    if len(cash) == len(tickets)+1:
        # 이미 경로를 정했는데 새로운 경로가 있을 경우
        if len(answer) == len(cash):
            j = 0
            # 기존 경로와 새로운 경로 중 알파벳 순서가 앞서는 경로를 찾기 위해 같은 index에서 서로 다른 공항값을 비교 
            while j < len(cash)-1 and answer[j] == cash[j]:
                j += 1
            first, second = answer[j], cash[j]
            if first > second:
                answer = deepcopy(cash)
        else:
            answer = deepcopy(cash)
        return

    for i in range(len(tickets)):
        if tickets[i][0] == node and not visited[i]:
            visited[i] = True
            cash.append(tickets[i][1])
            dfs(tickets[i][1], tickets, visited)
            # 백트래킹
            cash.pop()
            visited[i] = False
    return


def solution(tickets):
    global answer
    global cash
    cash = ['ICN']
    answer = []
    visited = [False for _ in range(len(tickets))]
    dfs(cash[-1], tickets, visited)
    return answer