(Python/LV3) 여행경로

문제출처: https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

풀이:

 

def solution(tickets):

    answer = []
    routes = dict() # 티켓 정보를 저장하는 딕셔너리

    for (start, end) in tickets:
        if start in routes:
            routes[start].append(end)
        else:
            routes[start] = [end]
    for i in routes.keys():
        routes[i].sort(reverse=True) # 뽑아야 하니깐 역순

    q = ["ICN"]
    while q:
        Top = q[-1]
        if (Top not in routes) or (not routes[Top]): # 더이상 방문할 곳이 없다 마지막 방문지점
            answer.append(q.pop())
        else:
            q.append(routes[Top].pop())
    
    return answer[::-1]



# print(solution([["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]))
print(solution([["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL", "SFO"]]))

 

첫번째 포문으로 출발지 에서 도착지 가는 딕셔너리 

두 번째 포문으로 도착지 알파벳 역순으로 >> 이유 나중에 뽑을때 더 빨리 나오니깐

 

시작 q에 인천

 

Top에서 시작하는 곳이 없거나 routes[Top]이 비어있지 않은 경우이다.

그러면 q에 append

그 외에 경우는 도착지점 q에 더함