학습 주제
DFS를 이용한 여행경로 문제 코드 구현

학습 내용

아이디어 & 알고리즘

• tickets 내의 원소들을 key를 출발지, value를 도착지로 하는 사전형으로 초기화
• 사전형이 key만 있다면 자료에 접근하기 쉽기 때문
• 주어진 제한사항에 여러 도착지가 있을 경우, 알파벳 순으로 빠른 곳을 먼저 방문.
• key 값 내 value를 역순으로 정렬 -> 이후 pop사용해서 사용
• 경로들을 임시로 저장할 stack[] 구현
• 답을 저장할 path[] 구현
• while len(stack[]) > 0, 재귀 구현
• top = stack[-1]
• 스택에서 출발지를 꺼냈을 때, 더 이상 방문할 경로가 없거나, 이미 방문을 소진해서 갈 수 없을 경우.
• if top not in routes or len(routes[key]) == 0
• path.append(stack.pop())
• 그렇지 않고, 갈 수 있는 경로가 있는 경우.
• else:
• stack.append(routes[top].pop())
• return path[::-1]

내 답안

def solution(tickets):
    routes = {}
    for t in tickets:
        routes[t[0]] = routes.get(t[0], []) + [t[1]]
    for key in routes:
        routes[key].sort(reverse = True)
    stack = ["ICN"]
    path = []
    
    while len(stack) > 0:
        top = stack[-1]
        if top not in routes or len(routes[top]) == 0:
            path.append(stack.pop())
        else:
            stack.append(routes[top].pop())
            
    return path[::-1]

어려운 점

크게 어려운 점은 없었다. 다만 새로운 문제에 바로 적용하려면 여러번 숙지가 필요할 것 같다.