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

일치하기만 할 뿐, 더 나은 답이 아닙니다.

---

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

알고가기

1. DFS

• 깊은 부분을 우선적으로 탐색하는 알고리즘
• 스택 or 재귀함수 사용

문제

주어진 tickets을 모두 이용하여 여행경로 짜려고 한다

방문하는 공항을 순서대로 담은 배열을 출력하라

조건

• 출발은 항상 'ICN'에서
• 모든 공항은 알파벳 대문자 세 자리
• 3 ≤ 공항의 수 ≤ 10,000
• ['ICN','SFO] => ICN 출발 SFO 도착 하는 티켓
• 경로가 두 개 이상일 시, 알파벳 순서

ex

tickets	return
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

반복	stack
1	['ICN']
2	['ICN', 'ATL']
3	['ICN', 'ATL', 'ICN']
4	['ICN', 'ATL', 'ICN', 'SFO']
5	['ICN', 'ATL', 'ICN', 'SFO', 'ATL']
6	['ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO']

나의 풀이

def solution(tickets):
    answer = []
    routes = {}		# 출발 공항과 도착 공항을 묶어줄 dict
    
    #['ICN','SFO'] + ['ICN','ATL'] => {'ICN' : ['SFO','ATL']}
    for ticket in tickets:
        routes[ticket[0]] = routes.get(ticket[0], []) + [ticket[1]]
    for route in routes:	# value 정렬
        routes[route].sort(reverse=True)
    # {
    # 'ICN': ['SFO', 'ATL'],
    # 'SFO': ['ATL'],
    # 'ATL': ['SFO', 'ICN']
    # }
    stack = ['ICN']
    
    while stack:
        begin = stack[-1]
        print(stack)
        # 출발지로서 존재하는지 and 방문 가능한 도착지가 존재하는지
        if begin in routes and routes[begin]:
            stack.append(routes[begin].pop())
        else:
            answer.append(stack.pop())
            
    answer.reverse()
    return answer