[ Lv 3 ] [ DFS ] 여행경로

풀이 과정

---

1. "ICN"이 시작점이므로, ICN에서 시작하여 DFS를 진행하면서, DFS의 깊이가 ticket의 길이까지 진행되는지 체크
   • 이 때, 가능한 경로가 2개 이상인 경우 알파벳 순서가 앞서는 경로를 return 해주어야 한다.
   • 따라서, 시작하기 전에 tickets의 2번째 요소([i][2]) 기준으로 오름차순 정렬 해 준다.
2. DFS를 진행하면서 정답과 방문여부에 push/pop 해주고, DFS를 ticket의 길이만큼 깊게 진행하였다면 정답 리스트를 출력해주면 된다.

• DFS의 이론은 알겠는데 Recursion에서 정답을 어떻게 표시해 주어야 할지 공부가 더 필요함..

---

소스 코드

end_flag = False
answer = []

def dfs(tickets, visited, city):
    global end_flag, answer
    if len(visited) == len(tickets):
        answer.append(city)
        end_flag = True
        return

    for i in range(len(tickets)):
        if tickets[i][0] == city and i not in visited:
            visited.add(i)
            answer.append(tickets[i][0])
            dfs(tickets, visited, tickets[i][1])
            if end_flag:
                return
            answer.pop()
            visited.remove(i)


def solution(tickets):
    global answer
    tickets.sort(key=lambda x:x[1])
    dfs(tickets, set(), "ICN")

    return answer

출처: 프로그래머스 코딩 테스트 연습, https://programmers.co.kr/learn/challenges