[DFS] Reconstruct Itinerary

Reconstruct Itinerary - LeetCode

from collections import defaultdict
def findItinerary(tickets):
    tickets.sort()
    d = defaultdict(list)
 
    for i in tickets:
        d[i[0]] += [i[1]]
 
 
    def dfs(locale):
        while d[locale]:
            new = d[locale].pop(0)  # pop()을 사용할 때는 for 문이아니라 while 문을 사용하자.
            dfs(new)
        result.append(locale)
 
    result = []
    dfs('JFK')
    return result[::-1]
 
# tickets =  [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
tickets = [["JFK", "SFO"], ["JFK", "ATL"], ["SFO", "ATL"], ["ATL", "JFK"], ["ATL", "SFO"]]
print(findItinerary(tickets))

---

Input
[["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]],
d = { 'JFK': ['KUL', 'NRT'], 'NRT': ['JFK'] }

Expected
["JFK","NRT","JFK","KUL"]

result = ['KUL', 'JFK', 'NRT', 'JFK']
result[::-1] = ["JFK","NRT","JFK","KUL"]

 

이 문제는 KUL과 같은 경우를 고려하여, result.append()을 적절하게 위치시켜야 풀 수 있다. KUL은 JFK에서 도착할 순 있어도, KUL에서 다른 도시로는 갈 수 없기 때문에 남은 도시들을 방문하기 위해선 KUL은 항상 마지막에 방문해야 한다.

 

dfs(locale)함수 호출 시, 나머지 도시들은 d[locale]이 존재하기 때문에 while문에 들어가게 된다.
하지만 KUL은 d[locale]이 존재하지 않으므로 while문을 건너뛰고 바로 result.append('KUL') 작업을 수행하게 된다.

이 문제에서는 result값을 [::-1]처리하기 때문에, 우선적으로 append()된다는 것은, 마지막에  방문한다는 의미와 같다.

만약 result.append()가 while문 위에 위치한다면, KUL과 d[locale]이 존재하는 도시의 경우를 구분짓지 못하고(KUL의 경우 우선적으로 추가되어야 한다) 추가될 것이다.

만약 result.append()가 while문 안에 위치한다면, KUL은 while문에 진입할 수 없으므로 추가되지 못할 것이다.

	dfs(locale) 호출 순서	result.append(locale) 순서
dfs(JFK)	1	4
dfs(KUL)	2	1
dfs(NRT)	3	3
dfs(JFK)	4	2

처음 방문한 지역('JFK')은 첫 번째 dfs('JFK')함수의 result.append('JFK')를 통해 추가되는데, 모든 result.append()의 작동과정 중 마지막에 발생한다.

 

++ 좋은 풀이 추가

from collections import defaultdict
 
 
def solution(tickets):
    d = defaultdict(list)
    for i, j in tickets:
        d[i].append(j)
    for i in d:
        d[i].sort()
    print(d)
 
    s = ['JFK']
    p = []
    while s:
        q = s[-1]
        if d[q] != []:  # 떠날 도시가 있다면 s에 append
            s.append(d[q].pop(0))
        else:  # 갈 도시가 없다면 결과에 추가
            p.append(s.pop())
        # print(f's={s}, p={p}')
    return p[::-1]
 
a = [["JFK","KUL"],["JFK","NRT"],["NRT","JFK"]]
print(solution(a))