프로그래머스 여행경로

dfs 풀이

answer= []

def solution(tickets):
    global answer
    start =[]
    N = len(tickets)
    for i in range(N):
        if tickets[i][0] == "ICN":
            for j in range(N):
                if j != i and tickets[i][1] == tickets[j][0]:
                    start.append((tickets[i][1], i))
                    break
    
    start.sort(key = lambda x:x[0])
    startidx = start[0][1]
    visited = [startidx]
    cur = tickets[startidx][1]
    ans = [tickets[startidx][0], tickets[startidx][1]]

    dfs(startidx, tickets, N, visited, cur, ans )
    return answer

def dfs(startidx, tickets, N, visited, cur ,ans):
    global answer
    if len(ans) == (N+1):
        if len(answer) == 0:
            answer = ans.copy()
        elif len(answer) != 0:
            for i in range(N+1):
                if ans[i] < answer[i]:
                    answer = ans.copy()
                    return
                elif ans[i] == answer[i]:
                    continue
                elif ans[i] > answer[i]:
                    return
        return 
    
    for i in range(N):
        if i not in visited and tickets[i][0] == cur:
            ans.append(tickets[i][1])
            visited.append(i)
            dfs(startidx, tickets, N, visited, tickets[i][1], ans)
            ans.pop()
            visited.pop()