첫 풀이 (1번 시간초과)
from collections import deque
from itertools import permutations
def solution(tickets):
answer = []
all_airport = set()
for line in tickets:
all_airport.update(line)
dic = list(all_airport) # 공항의 번호를 저장하는 사전
###print(dic)
n = len(dic)
m = len(tickets)
cases = permutations(tickets)
###print(list(cases))
for c in cases:
if c[0][0] != "ICN":
continue
check = [False] * n
index = dic.index("ICN")
check[index] = True
route = ["ICN"]
for idx in range(m):
if idx > 0 and c[idx-1][1] != c[idx][0]:
break
else:
route.append(c[idx][1])
index = dic.index(c[idx][1])
check[index] = True
if False not in check:
answer.append(route)
answer.sort(key = lambda x: (-len(x), x))
return answer[0]
두 번째 풀이 (1번만 실패)
from collections import deque
def solution(tickets):
answer = []
## 1. 주어진 항공권은 모두 사용해야 합니다. (키 조건)
## 2. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
m = len(tickets)
for i in range(m):
u, v = tickets[i]
if u == "ICN": ## 항상 "ICN" 공항에서 출발합니다.
check = [False] * m
check[i] = True
q = deque()
q.append(([u, v], check)) # 시작 공항(2개 짝), 어느 항공권을 사용했는지 표시 배열
####print('--시작-- ', i, q)
while q:
pre_q, pre_c = q.popleft()
####print(q)
if False not in pre_c: ## 종료 조건
if pre_q not in answer:
answer.append(pre_q)
break
for idx in range(m):
if pre_c[idx] == False and pre_q[-1] == tickets[idx][0]:
###q.append((pre_q, pre_c)) (디버깅) 1번. 현재 항공권 이용 안 하는 경우 빼주어야 5번에서 무한루프 해결됨..?
# 2번.
copy = pre_c[:] ## (디버깅) 이전 방문표시 배열(항공권에 대한)을 복사해주고 사용해야 함
copy[idx] = True
c = pre_q[:]
c.append(tickets[idx][1])
q.append((c, copy))
answer.sort()
return answer[0]
정답
- 1번은 알파벳 순으로 가장 앞의 정답을 출력해내지 못했던 것이 문제였었는지, tickets.sort()로 사전에 정렬 한 줄 해주고 수행하니 해결할 수 있었다.
from collections import deque
def solution(tickets):
answer = []
## 1. 주어진 항공권은 모두 사용해야 합니다. (키 조건)
## 2. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
m = len(tickets)
tickets.sort() ## 1번만 틀렸습니다. 나오다가 알파벳 순서를 미리 반영하기 위해 정렬 한 줄을 추가해 주었더니 바로 통과..!
for i in range(m):
u, v = tickets[i]
if u == "ICN": ## 항상 "ICN" 공항에서 출발합니다.
check = [False] * m
check[i] = True
q = deque()
q.append(([u, v], check)) # 시작 공항(2개 짝), 어느 항공권을 사용했는지 표시 배열
####print('--시작-- ', i, q)
while q:
pre_q, pre_c = q.popleft()
####print(q)
if False not in pre_c: ## 종료 조건
if pre_q not in answer:
answer.append(pre_q)
break
for idx in range(m):
if pre_c[idx] == False and pre_q[-1] == tickets[idx][0]:
###q.append((pre_q, pre_c)) (디버깅) 1번. 현재 항공권 이용 안 하는 경우 빼주어야 5번에서 무한루프 해결됨..?
# 2번.
copy = pre_c[:] ## (디버깅) 이전 방문표시 배열(항공권에 대한)을 복사해주고 사용해야 함
copy[idx] = True
c = pre_q[:]
c.append(tickets[idx][1])
q.append((c, copy))
answer.sort()
return answer[0]
