[프로그래머스 LV 3] 여행경로 (파이썬/python)

https://programmers.co.kr/learn/courses/30/lessons/43164?language=python3 

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

 

 

옛날에 손도 못 댔던 문제들을 풀고있다...

약간 감격스러움.. 이 문제도 몇달전에는 풀다가 포기했던 문제다..

 

 

정렬함수를 이용해서 도착지를 오름차순으로 정렬해줬다.

 

모든 경우를 dfs와 백트래킹으로 돌며 가능한 경로를 answer에 담았다.

첫번째 answer에 담길 값만 찾으면 된다.

정렬을 통해 이미 오름차순 조건은 충족시킨 상태이다!

 

찾을경우 True를 반환해서 더 이상 탐색은 그만두게 설정했다

 

 

answer = []
visit = []
li = []
 
 
def dfs(arr, tickets, cnt):
    global visit, li, answer
 
    if cnt == len(tickets):
        li.append(arr[1])
        answer = li[:]
        li.pop()
        return True
    for i in range(len(tickets)):
        if arr[1] == tickets[i][0]:
            if visit[i] == 1:
                continue
 
            visit[i] = 1
            # print(li,arr)
            li.append(arr[1])
            flag = dfs(tickets[i], tickets, cnt + 1)
            if flag:
                return True
            visit[i] = 0
            li.pop()
    return False
 
 
def solution(tickets):
    global visit, li
 
    # 도착지 빠른순으로 정렬
    tickets = sorted(tickets, key=lambda x: (x[1]))
    for i in range(len(tickets)):
        if tickets[i][0] == "ICN":
            visit = [0] * len(tickets)
            li = ["ICN"]
            visit[i] = 1
            flag = dfs(tickets[i], tickets, 1)
            if flag:
                return answer