[프로그래머스] 여행 경로 by 파이썬(Python) : DFS

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

프로그래머스

 

난이도

LV3

 

 

문제 설명 

• [출발지,도착지] 형태로 적힌 항공권 정보 List가 주어진다.
• 출발지는 항상 ICN 공항에서 출발하며 모든 항공권을 사용해야 한다. 
• 이를 만족하는 경로를 Return하고
• 만약 만족하는 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 Return한다.

 

접근법

1. 스택에 ICN을 넣어준다.
2. 출발지와 도착지 정보가 담긴 dictionary 배열의 key(출발지) 와 value(도착지)리스트 를 이용해 담아준다.
3. 알파벳 순서대로 티켓을 사용하기 위해 각 key에 대해 value(도착지) 리스트를 역순으로 정렬해준다. => (pop으로 꺼내기 때문에 역순 정렬)
4. 스택이 비어있지 않다면 스택의 마지막 값을 꺼낸다.
5. 만약 마지막 도착지로 부터 더 이상 갈 도착지가 없다면 return해줄 배열에 추가한 후 스택에서 제거해준다.
6. 다음 도착지로 갈 수 있다면 다음 도착지를 스택에 추가해준 후 해당 도착지를 dictionary에서 제거해준다.
7. 역순으로 return해준다.

 

코드

def solution(tickets):
    answer = []
    dic = {}
    stack = ["ICN"]
    for s, e in tickets:
        if s not in dic:
            dic[s] = [e]
        else:
            dic[s].append(e)
    
    for k in dic.keys():
        dic[k].sort(reverse=True)
    
    while stack:
        top = stack[-1]
        #더 이상 갈 수 있는 도착지가 없을때
        if (top not in dic) or (not dic[top]):
            answer.append(stack.pop())

        else:
            stack.append(dic[top].pop())

    return answer[::-1]