[프로그래머스] 여행경로 -Python

문제 후기

1. (만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.) 해당 제한사항을 가능한 이라는 것을 인지하지 못하고 단순하게 알파벳이 먼저 오면 해결하려 해서 틀리게 됐습니다.
2. DFS와 알파벳 순서 2가지를 생각해보며 다시 알고리즘을 짰고 스택을 활용하여 문제를 풀었습니다.
3. 해당 알고리즘의 경우 도착 or 항공편이 없는 경우 먼저 answer에 들어가게 했으며 마지막에 reverse를 통해 결과값을 제출했습니다.

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

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

def solution(tickets):

    node_dict = {}      # 노드 hash화
    # 출발지를 key로 도착지를 value로 지정.
    for city in tickets:
        # dict.get(a,b) = dict에서 key가 a인 것을 찾고 없으면 b값을 넣겠다.
        node_dict[city[0]] = node_dict.get(city[0], []) + [city[1]]

    # 알파벳 역순으로 정렬
    for city in node_dict:
        node_dict[city] = sorted(node_dict[city], reverse=True)


    stack = ["ICN"]
    answer = []

    # 스택에 값이 있는동안 계속 반복
    while stack:
        now_city = stack[-1]
        # 만약 해당 도시 출발 항공표가 없을 때 answer에 추가.
        if now_city not in node_dict or node_dict[now_city] == []:
            answer.append(stack.pop())
        else:
            # 해당 도시 출발 항공표가 있을 때 다음 도시 pop해서 스택에 추가
            stack.append(node_dict[now_city].pop())
    # 역순이므로 다시 정렬
    answer.reverse()
    return answer