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

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

프로그래머스

 

• 주어진 항공권을 모두 이용하여 여행경로 짜기
• 항상 "ICN" 공항에서 출발
• tickets: 항공권 정보가 담긴 2차원 배열
• 방문하는 공항 경로를 배열에 담아 return

제한사항

• 모든 공항은 알파벳 대문자 3글자로 이루어짐
• 주어진 공항 수는 3개 이상 10,000개 이하
• tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미
• 주어진 항공권은 모두 사용해야 함
• 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return
• 모든 도시를 방문할 수 없는 경우는 주어지지 않음

 

"""
입출력 예시)

tickets = [["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]] -> ["ICN", "JFK", "HND", "IAD"]
tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] -> ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
"""

# tickets = [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] -> ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

# ["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 
# ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞서기 때문에 이 경로를 return

 

 

## 의사 코드 ##

# 주어진 항공권을 모두 이용 -> DFS
# stack 

# tickets를 딕셔너리 그래프 형태로 만들기
# defaultdict(list)

# 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return
# -> DFS 수행할 때 노드 중 알파벳 순서가 더 앞에 있는 것을 방문
# for k in graph.keys():
#   graph[k].sort(reverse=True)
#       -> stack 구조를 사용할 것이기 때문에 역순으로 정렬해야 알파벳 순서로 꺼내짐

 

 

 

통과한 코드

 

from collections import defaultdict
def solution(tickets):
    answer = []
    # 그래프에 정보 입력 
    graph = defaultdict(list)
    for start, arrive in tickets:
        graph[start].append(arrive) # 방향 그래프니까 한 번만 append 

    # 알파벳 순으로 정렬
    for k in graph.keys():
        graph[k].sort(reverse=True) # stack 구조를 사용할 것이기 때문에 역순으로 정렬

    q = ["ICN"] # stack
    while q:
        city = q[-1] # => q.pop()할 값
        if city not in graph or len(graph[city]) == 0:
            answer.append(q.pop())
        else:
            q.append(graph[city][-1]) 
            graph[city] = graph[city][:-1]
    # answer 역순 정렬
    answer.reverse()
    return answer

-> tickets의 정보를 graph라는 dict로 생성, stack을 활용한 DFS

 

stack 구조를 사용하기 때문에 graph의 values를 정렬할 때 역순으로 정렬하는 것에 주의

 

 

• 과정 확인

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

"""
정렬 전 graph: defaultdict(<class 'list'>, {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})
정렬 후 graph: defaultdict(<class 'list'>, {'ICN': ['SFO', 'ATL'], 'SFO': ['ATL'], 'ATL': ['SFO', 'ICN']})
시작 q: ['ICN'] 

city: ICN
graph[city][-1]: ATL
슬라이싱 전 graph[city]: ['SFO', 'ATL']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL']
남은 graph[city]: ['SFO'] 

city: ATL
graph[city][-1]: ICN
슬라이싱 전 graph[city]: ['SFO', 'ICN']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL', 'ICN']
남은 graph[city]: ['SFO'] 

city: ICN
graph[city][-1]: SFO
슬라이싱 전 graph[city]: ['SFO']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL', 'ICN', 'SFO']
남은 graph[city]: [] 

city: SFO
graph[city][-1]: ATL
슬라이싱 전 graph[city]: ['ATL']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL', 'ICN', 'SFO', 'ATL']
남은 graph[city]: [] 

city: ATL
graph[city][-1]: SFO
슬라이싱 전 graph[city]: ['SFO']
--------------------------------------------------
graph[city][-1] append 후 q: ['ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO']
남은 graph[city]: [] 

city: SFO
city pop 후 q: ['ICN', 'ATL', 'ICN', 'SFO', 'ATL'] 

city: ATL
city pop 후 q: ['ICN', 'ATL', 'ICN', 'SFO'] 

city: SFO
city pop 후 q: ['ICN', 'ATL', 'ICN'] 

city: ICN
city pop 후 q: ['ICN', 'ATL'] 

city: ATL
city pop 후 q: ['ICN'] 

city: ICN
city pop 후 q: [] 

역순 정렬 전 answer: ['SFO', 'ATL', 'SFO', 'ICN', 'ATL', 'ICN']

['ICN', 'ATL', 'ICN', 'SFO', 'ATL', 'SFO']
"""

 

 

 

다른 풀이

 

def solution(tickets):
    answer = []
    
    visited = [False]*len(tickets)
    
    def dfs(airport, path):
        if len(path) == len(tickets)+1:
            answer.append(path)
            return
        
        for idx, ticket in enumerate(tickets):
            if airport == ticket[0] and visited[idx] == False:
                visited[idx] = True
                dfs(ticket[1], path+[ticket[1]])
                visited[idx] = False
        
        
    dfs("ICN", ["ICN"])
    
    answer.sort()

    return answer[0]

-> graph를 따로 생성하지 않고, 재귀를 활용한 DFS

 

 

참고)

 

https://gurumee92.tistory.com/165

프로그래머스 문제 풀이 여행 경로

 

https://lottegiantsv3.tistory.com/27

여행 경로 - 파이썬(Python)