Algorithms / Programmers / 여행경로

링크

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

풀이

• 경로를 역순으로 저장하기 때문에 마지막에 경로의 역순을 출력해주면 경로가 나온다.
• 테스트 예제 1,2번의 경우 정렬한 순서대로 따라갔을때 여행을 완주하지 못하는 경우가 나온다.
• stack과 path를 따로 저장
  • stack의 맨 위 여행표(top)는 dfs방식으로 routes를 추적한다(스택은 ICN부터 시작해 dfs적용).
  • 추적하다 표가 남아있는데 완주를 못한 경우가 나오면 path에 저장 및 스택 팝, 새로운 탑.
  • top이 routes에 있다면 stack에 저장 및 routes에서 삭제.
• 스택이 남아있다면 위의 들여쓰기 반복

코드

from collections import defaultdict

def printDictList(dict):
    for key in dict:
        print(key,':', end=' ')
        for value in dict[key]:
            print(value, end=' ')
        print()
    print()

def makeDict(tickets):
    routes = defaultdict(list)
    for departure, arrival in tickets:
        routes[departure].append(arrival)
    return routes

def dfs(routes):
    stack = ["ICN"] # Initial airport code
    path = []
    while len(stack) > 0:
        top = stack[-1]
        # top is not in routes or there is not routes[top]
        if top not in routes or len(routes[top]) == 0:
            path.append(stack.pop())
        else: # top is in routes or len(routes[top])>0
            stack.append(routes[top].pop(0))
    return path[::-1]
    
def solution(tickets):
    answer = []
    
    # tickets into dictionary 
    routes = makeDict(tickets)
    
    # sorting routes
    for r in routes:
        routes[r].sort()
        
    answer = dfs(routes)
    return answer