[코딩테스트/프로그래머스/Python]여행경로

💡생각

1. tickets배열을 튜플형식으로 deque에 넣음.
2. 처음엔 변수에 ICN 저장.
3. deque에서 하나를 꺼내 출발지가 변수와 동일한지 판단.
4. 동일하다면 그 변수로 시작하는 것이 두 개 이상일 경우 알파벳 순서가 더 높은지 판단.
5. 아니라면 다시 deque에 넣고 맞다면 변수에 그 도착지를 저장하고 answer배열에 도착지 append함.
6. deque이 빌 때까지 반복함.

⏬다른사람의 코드

코드짜기가 너무 어렵고 시간이 너무 흘러서 다른 사람의 코드를 보기로 함.

🔗풀이 참고
https://gurumee92.tistory.com/165

def solution(tickets):
    # 1. 그래프 생성
    routes = dict()

    for (start, end) in tickets:
        routes[start] = routes.get(start, []) + [end]  

    # 2. 시작점 - [끝점] 역순으로 정렬    
    for r in routes.keys():
        routes[r].sort(reverse=True)

    # 3. DFS 알고리즘으로 path를 만들어줌.
    st = ["ICN"]
    path = []
    
    while st:
        top = st[-1]

        if top not in routes or len(routes[top]) == 0:
            path.append(st.pop())
        else:
            st.append(routes[top][-1])
            routes[top] = routes[top][:-1]
    
    # 4. 만든 path를 거꾸로 돌림.
    answer = path[::-1]
    return answer

1. {시작점 - [도착점들]}쌍의 그래프 만듦.
2. 도착점들의 리스트는 역순으로 정렬
3. DFS 알고리즘을 통해 모든 점 순회.
   3-1. 문제 조건에 따라 "ICN"을 스택에 먼저 넣음.
   3-2. 스택이 빌때까지 반복.
   (1). 스택에서 가장 위의 저장된 데이터 top을 꺼냄.
   (2). 만약 top이 그래프에 없거나, top을 시작점으로 하는 티켓이 없는 경우, 스택에서 꺼내와 path에 저장.
   (3). (2)번이 아니라면 top을 시작점으로 하는 끝점 중 가장 마지막 지점을 꺼내와 스택에 저장.
4. 이렇게 해서 얻어온 path를 역순으로 만듦.

🔗프로그래머스 - 여행경로
https://programmers.co.kr/learn/courses/30/lessons/43164