알고리즘 고득점 Kit - 여행경로(DFS)

문제 풀이

DFS + 백트래킹으로 접근하여 풀었습니다.

1. visited를 이용해서 사용한 티켓 판별
2. dfs 종료 조건은 방문한 여행지가 전체 티켓의 개수 + 1인 경우(조건이 모든 여행지를 간다고 했으므로)
3. 티켓의 출발지와 path(방문지)의 마지막이 같고 사용하지 않은 티켓인 경우 dfs 사용
4. path.pop을 해줘야 원래 상태로 돌아감
5. 리스트에 ICN을 넣은 상태로 하면 첫 출발지는 ICN으로 고정 가능

def solution(tickets):
    answer = []
    tickets.sort()
    N = len(tickets)
    visited = [False] * N

    def dfs(path):
        if len(path) == N+1:
            answer.append(path[:])
            return 

        for i in range(N):
            if tickets[i][0] == path[-1] and visited[i] == False:
                visited[i] = True
                path.append(tickets[i][1])
                dfs(path)
                path.pop()
                visited[i] = False

    dfs(["ICN"])

    return answer[0]