여행경로
레벨3, 깊이/너비 우선 탐색(DFS/BFS)
이 문제는 예전에 알고리즘 책으로 공부 할 때 한번 풀었던 문제와 거의 동일했습니다. 그래서 그런지, 생각보다 쉽게 풀었습니다.
1. 문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
['출발지', '목적지'] 의 형태로 이루어진 항공권들이 주어지고, 이를 모두 활용해서 모든 공항을 방문하는 경로를 return 하는 문제입니다.
2. 제한사항
1. 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
2. 주어진 공항 수는 3개 이상 10,000개 이하입니다.
3. tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
4. 주어진 항공권은 모두 사용해야 합니다.
5. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
6. 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
3. 사고과정 / 나의 풀이
가장 좋은 점은 모든 도시를 방문할 수 없는 경우를 우리가 골라내지 않아도 된다는 점입니다. 이부분에서 굉장히 부담이 줄었습니다.
우선 출발-도착 조합을 활용해서 일종의 지도를 하나 만들어 두고, 이것을 활용해서 문제를 풀어야 할 것 같습니다. 그리고 조건으로 주어진 것 중에서, 알파벳 순서가 앞서는 경로를 우선 리턴해야한다는 점에도 유의해야겠습니다.
1. dict를 활용해서 출발-도착지를 표현할 수 있을 것 같다.
2. 반복적으로 이 지도를 따라가도록 한다.
3. 이 때 다음 목적지는 알파벳 순으로 정한다.
이것을 코드로 표현하자면 아래와 같다. 작성하다보니 1 - 3 - 2 순서가 더 적합한 것 같았다.
from collections import defaultdict
def solution(tickets):
MAP = defaultdict(list)
for st, ds in tickets:
MAP[st].append(ds)
for m in MAP:
MAP[m].sort(reverse=True)
answer = []
def dfs(st):
while MAP[st]:
dfs(MAP[st].pop())
answer.append(st)
dfs('ICN')
return answer[::-1]
그런데, MAP의 원소를 하나하나 뽑아서 재정렬 해 주는 것 보다, 주어진 ticket을 정렬해서 넣는 것이 코드가 더 깔끔할 것 같습니다.
from collections import defaultdict
def solution(tickets):
MAP = defaultdict(list)
for st, ds in sorted(tickets, reverse = True):
MAP[st].append(ds)
answer = []
def dfs(st):
while MAP[st]:
dfs(MAP[st].pop())
answer.append(st)
dfs('ICN')
return answer[::-1]
아무래도, 주어지는 모든 경우에서 완주가 가능하고, 모든 티켓을 사용해야한다는 조건 덕분에 오히려 문제가 쉬워진 것 같습니다.
3. 다른 사람의 풀이
맨 위, 첫번째 풀이
from collections import defaultdict
def dfs(graph, N, key, footprint):
print(footprint)
if len(footprint) == N + 1:
return footprint
for idx, country in enumerate(graph[key]):
graph[key].pop(idx)
tmp = footprint[:]
tmp.append(country)
ret = dfs(graph, N, country, tmp)
graph[key].insert(idx, country)
if ret:
return ret
def solution(tickets):
answer = []
graph = defaultdict(list)
N = len(tickets)
for ticket in tickets:
graph[ticket[0]].append(ticket[1])
graph[ticket[0]].sort()
answer = dfs(graph, N, "ICN", ["ICN"])
return answer
제 풀이와 비슷한 듯 다른 풀이이기도 하고, pop과 insert를 같이 사용했다는 부분이 새로운 풀이인것같습니다. 아마 graph에서 지금 들어간 출발지만을 제외하고자 하는 의도가 있는 것 같은데, 솔직히 깊은 의미까지는 잘 이해하지 못했습니다.. ㅠㅠ
def solution(tickets):
routes = {}
for t in tickets:
routes[t[0]] = routes.get(t[0], []) + [t[1]]
for r in routes:
routes[r].sort(reverse=True)
stack = ["ICN"]
path = []
while len(stack) > 0:
top = stack[-1]
if top not in routes or len(routes[top]) == 0:
path.append(stack.pop())
else:
stack.append(routes[top][-1])
routes[top] = routes[top][:-1]
return path[::-1]
일단은 defaultdict 없이, get 함수를 통해 routes를 만들었습니다. 여기부터가 정말 새로웠고, 재귀가 없다는 점에서 코드 자체도 깔끔하고 속도도 빨랐습니다. 다만 궁금한 점은 마지막 부분에서 왜 pop대신 slicing을 사용했을까..? 하는 궁금증이 조금 남았습니다.
## 참고 - pop(), slicing 속도 비교 ##
import timeit
t1 = timeit.Timer('a=50000*[\'a\'];a.pop()')
t2 = timeit.Timer('b=50000*[\'b\'];b[:-1]')
r1 = t1.timeit(10000)/10000
r2 = t2.timeit(10000)/10000
print(r1)
print(r2)
print(f'pop이 더 빠른가? {r1<r2}')
print(f'pop이 몇 배 더 빠른가? {r2/r1}')
# 8.113919620000001e-05
# 0.00022016935049999997
# pop이 더 빠른가? True
# pop이 몇 배 더 빠른가? 2.713477096289006