알파벳 순서로만 경로를 추가하면 모든 티켓을 사용해서 경로 완성이 불가능한 경우의 수가 존재하는 것 같다.
from collections import defaultdict
def solution(tickets):
# {출발지 : [도착지]} 저장하기
graph = defaultdict(list)
for s, e in tickets:
graph[s].append(e)
for k in graph: # 도착지가 여러개면 알파벳 순으로 정렬
graph[k].sort(reverse=True)
n = len(tickets)
answer = ["ICN", ]
for _ in range(n):
now = answer[-1]
now = graph[now].pop()
answer.append(now)
return answer
풀이 2
BFS 이용해 모든 티켓을 사용한 경우에만 경로를 추가하도록 한다.
from collections import deque
def solution(tickets):
answer = []
# (현재 위치, 지금까지 경로, 사용 가능한 티켓 번호)
q = deque([("ICN", ["ICN"], set([i for i in range(len(tickets))]))])
while q:
now, path, visitable = q.popleft()
# 모든 티켓 사용하면 해당 경로 추가하기
if not visitable:
answer.append(path)
# 사용 가능한 티켓이고, 시작 위치가 현재 위치와 가능한 경우
for idx in visitable:
start, dest = tickets[idx]
if start == now :
q.append((dest, path+[dest], visitable-{idx}))
return sorted(answer)[0]
풀이 3
DFS 사용해서 모든 경로를 확인하지 않고, 단 하나의 경로만 확인하기
알파벳 순으로 갔다가, 불가능한 경로일 때 다시 되돌아와야 한다.
stack으로 현재 경로를 저장하고, 다음에 갈 수 있는 경로를 알파벳 순서로 추가한다.
마지막에 도달했을 때(다음에 갈 수 있는 경로가 없을 때) 해당 위치를 정답 경로에 추가한다.
갈 수 있는 경로가 없다는 뜻은 해당 위치가 '마지막' 이라는 의미다.
from collections import defaultdict
def solution(tickets):
# {출발지 : [도착지]} 저장하기
graph = defaultdict(list)
for s, e in tickets:
graph[s].append(e)
for k in graph: # 도착지가 여러개면 알파벳 순으로 정렬
graph[k].sort(reverse=True)
n = len(tickets)
now = "ICN"
stack = ["ICN"] # 현재 경로
answer = [] # 정답 경로
while stack :
now = stack[-1] # 현재 위치
# 현재 위치에서 다음에 갈 수 있는 경로가 없을 때,
# 즉 마지막 위치를 정답 경로에 추가하기
if now not in graph or not graph[now]:
answer.append(stack.pop())
# 다음에 갈 수 있는 경로가 있으면 알파벳 순서로 추가하기
else:
stack.append(graph[now].pop())
return answer[::-1]
