PROBLEM
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
[제한사항]
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 ^알파벳 순서가 앞서는 경로^를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
MY SOLUTION
1st 시도: FAIL🧐
DAG로 착각하고 위상정렬 풀듯이 풀었는데 사이클이 존재할 수 있는 구조였다(입출력 예에도 있다..).
그런데 DAG에서 acyclic이 빠진 그래프였고, 약간 비튼 DAG 같았다.
2nd 시도: FAIL🧐
프로그래머스 그래프 문제 가장 먼 노드를 풀다가 collections의 defaultdict을 알게 되고 아싸리 써먹어야지🤗 하고 신나게 풀었는데 테스트케이스 1번을 통과하지 못했다😂.
질문하기에서 찾아 보니까 출발지, 도착지가 같은 티켓이 tickets에 1개 이상 들어오는 경우(아래 참고)가 반례였다.
이 반례에서 answer이 제대로 출력된다면, 질문하기에 다른 반례들도 많으니 참고하시길..!
# 반례
tickets = [['ICN', 'A'], ['ICN', 'A'], ['A', 'ICN'], ['A' , 'C']]
# 여기서 tickets[0]과 tickets[1]의 출발 공항과 도착 공항이 동일한 걸 볼 수 있다.
answer = ['ICN', 'A', 'ICN', 'A', 'C']3rd 시도: SUCCESS🥳
위 반례를 적극 반영하여 defaultDict에 tickets 정보를 저장할 때 잔여 티켓 수로 저장하였고, 이 과정에서 try except 문을 사용하였다(getGraph 함수 참고).
from collections import defaultdict
graph = defaultdict(dict)
# (예) graph = defaultdict(<class 'dict'>, {'ICN': {'A': 2}, 'A': {'ICN': 1, 'C': 1}})
answer = []
def solution(tickets):
global graph
getGraph(tickets)
dfs('ICN')
answer.reverse()
return answer
def dfs(ap):
# * graph에 담긴 ticket들 알파벳 순으로 소모하기
# a = 연결된 노드의 개수, 평균 O(aloga * v + e)으로 추정.
# aloga = sorted(graph[ap])
global graph
for dest in sorted(graph[ap]):
if graph[ap][dest] > 0:
# 방문 시 티켓 소모, 스택에 넣어두기
graph[ap][dest] -= 1
dfs(dest)
# dfs, 가장 깊은 노드부터 기록 -> solution에서 reverse해 줌
answer.append(ap)
def getGraph(tickets):
# * graph에 tickets 정보 저장
# O(len(tickets))
global graph
for a1, a2 in tickets:
try:
if graph[a1][a2] > 0:
# ! 2번 시도 반례 고려
# 반례 = 출발도착이 같은 티켓이 2개 이상 있는 경우: graph에 방향과 해당 내용의 티켓 수 정보 저장.
graph[a1][a2] += 1
except:
graph[a1][a2] = 1
-
graph: 위 적은 예와 같이 defaultdict() 안에 각 key에 대응하는 value는 dict()의 형태를 가진다.
동일 내용을 가진 티켓의 개수와 티켓의 도착지를 표현할 수 있게
ICN(출발지) => A(도착지): 2개(동일 내용 티겟 개수), A => ICN: 1개, A => C: 1개를
{'ICN': {'A': 2}, 'A': {'ICN': 1, 'C': 1}}
이렇게 저장할 수 있는 형태로 중첩된 dict 자료형을 택하게 되었다. -
answer.reverse(): dfs()에서 언급했듯이, answer에 해당 공항을 추가하는 게 가장 마지막에 이뤄지는 일이다(for문으로 dfs()를 재귀 호출한 이후에 answer에 추가). 즉, "완벽한" 여행 경로의 마지막에, 기억을 되짚어보면서 가장 최근에 갔던 공항 순서대로 적은 게
answer리스트다.
예시: answer = ['C', 'A', 'ICN', 'A', 'ICN']
이런 리스트를 여행 경로의 바른 순서대로 적으려면 reverse하면 된다.
물론 더 좋은 방법이 있을 수 있다. DAG에서 시작해서 푸느라 이렇게 된 거긴 하다...
