프로그래머스 Lv3 여행경로

 

 DFS, BFS 를 배우고 나서 프로그래머스의 문제를 접하게 되었다. 

 

문제는 아래와 같다.

 

 

---

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

제한사항

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

입출력 예

ticketsreturn

[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]	["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]	["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]

입출력 예 설명

예제 #1

["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.

예제 #2

["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.

---

주어진 tickets의 정보는 출발지와 도착지가 정해져 있다. 그리고 무조건 'ICN' 인천에서 출발을 정의한다.

 

프로그래머스의 예시 중 tickets 이 [["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]] 인 경우를 예로 들어 아래의 코드를 살펴보자.

먼저 출발지와 도착지 정보를 dictionary 형태로 저장을 해주자. 

아래의 defaultdict 함수를 사용해서 {'출발지': ['도착지', '도착지', '도착지' , ... ...]} 와 같은 형태로 만들어 준다. 두번째 for 문에서는 문제에서 알파벳 순으로 빠른 것을 우선으로 하라고 명시하여 만들어진 dictionary에 value를 sort해 주었다.

from collections import defaultdict

trip_advisor = defaultdict(list)
for t in tickets:
    trip_advisor[t[0]].append(t[1])

for t in trip_advisor:
    trip_advisor[t] = sorted(trip_advisor[t])

 

위의 코드를 실행하게 되면 trip_advisor는 아래와 같은 형태를 갖는다. key는 출발지, 그리고 value는 리스트안에 도착지들로 구성된다.

defaultdict(list,
            {'ICN': ['ATL', 'SFO'], 'SFO': ['ATL'], 'ATL': ['ICN', 'SFO']})

 

출발지가 항상 'ICN' 인천이라고 하여 departure를 'ICN'으로 정의한다. 그리고 가장 먼저 stack에 담아준다. stack의 역할은 DFS에서 내가 살펴본 노드들을 쌓는 곳이다. 즉 도착지를 다니면서 그 도착지들을 stack에 차곡차곡 쌓는다. routes의 역할은 stack에 살펴본 노드들이 전부 쌓이고 나면 하나씩 담아서 경로로 표현하도록 한다.

departure = 'ICN'
stack = [departure]
routes = []

 

while 문에 stack이 모두 소진될 때까지 진행하도록 한다.

plane은 현재 비행기인데, 출발지라고 보면 된다. 처음에는 stack[-1]이 'ICN'에 위치해 있다. if 문에 담긴 내용은 처음 'ICN'을 기준으로 말하면 'ICN'이 trip_advisor의 key들 중에 존재하고(출발지로써 주어진 티켓), 그리고 'ICN'에서 출발하여 도착지가 담긴 티켓이 존재하면 도착지 티켓중에서 알파벳순이니까 앞에거 먼저 사용하여 stack에 담는다. 

 문제에서 주어진 모든 티켓이 다 사용되고, 모든 도시를 돈다고 했으니 계속해서 key는 value를 부르고 value를 다시 key로 하여 또 value 중에서 가장 알파벳이 빠른 것을 또다시 key로 삼고, 이것이 반복되다가 보면 trip_advisor에 value들이 모두 소진되는 때가 온다.

 그 때부터 else문이 작동하면서 stack.pop() 이 stack 개수만큼 작동하면서 routes 변수에 append 된다.

while stack:
    plane = stack[-1]
    if plane in trip_advisor and trip_advisor[plane]:
        stack.append(trip_advisor[plane].pop(0))
    else:
        routes.append(stack.pop())    

 

전에 필기한 탐색알고리즘에서 먼저 네트워크 구성을 해야되는 것을 보았는데, 이처럼 주어지는 데이터 형식이 달라서 어떤식으로 네트워크를 표현할 지를 결정하는 것이 중요한 것 같다. 본 문제에서 사용한 네트워크 구조 형태는 아래의 포스팅에서 예시로 보았던 network1과 같은 dictionary 형태로 구성한 것이다.

data-science-hi.tistory.com/171

탐색 알고리즘 BFS(Breath-first search)와 DFS(Depth-first search)

 

 

아래는 제출을 위해 위의 코드들을 합친 것이다.

from collections import defaultdict

def solution(tickets):

    trip_advisor = defaultdict(list)

    for t in tickets:
        trip_advisor[t[0]].append(t[1])
    for t in trip_advisor:
        trip_advisor[t] = sorted(trip_advisor[t])

    departure = 'ICN'
    stack = [departure]
    routes = []
    
    while stack:
        plane = stack[-1]
        if plane in trip_advisor and trip_advisor[plane]:
            stack.append(trip_advisor[plane].pop(0))
        else:
            routes.append(stack.pop())

    return routes[::-1]

 

 

 

 

ref)

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

wwlee94.github.io/category/algorithm/bfs-dfs/travel-route/