[Python] programmers 여행 경로

1. 문제 링크

https://programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

2. 문제 요약

방문하는 공항 경로를 배열에 담아 return

3. 아이디어 정리

• 백트래킹으로 진행합니다.

1. 처음 ICN를 배열에 담아 넘겨줍니다.
2. 티켓들 중 마지막으로 탐색한 값과 시작값이 같은 티켓 & 방문 안한 경우 재귀를 진행합니다.

 

4. 문제 풀이

4-1. 내 풀이

"""
 항상 ICN 공항에서 출발
 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
"""
import copy
first = True
def solution(tickets):
    def dfs(arr):
        global first
        global answer
        if len(tickets) + 1 == len(arr):  # 1. Base condition(종료 조건)
            if first:
                answer = copy.deepcopy(arr)
                first = False
            return
				# 2. 백트래킹. 다음으로 갈수 있는 모든 티켓 사용 
        for i, a in enumerate(tickets):
            s, e = a
            if arr[-1] == s and not visit[i]:  # 마지막 방문 도시 == 현재 시작 도시 & 방문 안한 경우 
                arr.append(e)
                visit[i] = True
                dfs(arr)
                arr.pop()
                visit[i] = False
    visit = [False] * len(tickets)
    tickets.sort()
    dfs(["ICN"])
    return answer

 

 

5. 결론

• 백트래킹