문제 링크
https://school.programmers.co.kr/learn/courses/30/lessons/43164
문제 유형
DBS/BFS
🌈 문제
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입력
tickets :[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]출력
["ICN", "JFK", "HND", "IAD"]💡 아이디어
이 문제는 인덱스를 숫자로 이용할 수 없고 문자열로 존재하기 때문에 문자열 리스트를 이용하기 위해서는 딕셔너리를 이용해야 한다. 그런데 파이썬의 일반적인 딕셔너리를 사용하기에는 많은 불편함이 있으므로 defaultdict 을 이용하여 조작하기 쉽게 해야 한다.
defaultdict이 무엇인지 알아보자.
먼저 이번 문제에서는 src 값이 딕셔너리 안에 존재하는지 확인하고, 존재하지 않는다면 list 로 키에 대한 값을 세팅해 준 뒤에 그 list에 dist 값을 차례로 append해야 하는 상황이었다. 그런데, 딕셔너리 내에 값이 존재하는지 존재하지 않는지를 하나씩 일일이 확인해야 하는 과정이 매우매우 귀찮게 느껴진다. 이럴 때에는 defaultdict 자료형을 사용할 수 있다.
from collections import defaultdict해당 코드를 통해서 모듈을 미리 불러오도록 하고, 이후 기본값으로 어떤 자료형을 사용할 것인지 넘겨주기만 하면 된다.
graph = defaultdict(list)짜잔. 그러면 이제 dict을 자유롭게 사용 가능하다.
어떻게 풀어야 하는데?
이 문제는 최단거리를 구하는 문제도 아니고 갈 수 있는 경로를 출력해야 하므로 그래프 개념으로 떠올렸고, DFS로 풀어야 한다는 것을 알 수 있었다. DFS 하면 재귀함수와 stack이 떠오르는데, 이 문제는 정답이 여러 개 있을 수 있는데 그 중에서 알파벳이 빠른 순서대로 출력한다는 관점에서 stack으로 풀이하는 것이 더욱 쉽고 빠르게 풀이할 수 있는 것으로 보이므로 stack을 바탕으로 코드를 작성해보자.
👨💻 코드 작성
from collections import defaultdict
def solution(tickets):
graph = defaultdict(list)
answer = []
for src, dest in tickets:
graph[src].append(dest)
for key in graph:
graph[key].sort(reverse=True)
stack = ['ICN']
answer = []
while len(stack) > 0:
src = stack[-1]
if graph[src] and len(graph) > 0:
stack.append(graph[src].pop())
else:
answer.append(stack.pop())
answer.reverse()
return answer코드를 하나하나 뜯어보면서 어느 부분을 어떻게 작성했는지 확인해 보자.
graph = defaultdict(list)
answer = []
for src, dest in tickets:
graph[src].append(dest)defaultdict 자료형을 이용하여 list로 초기화를 해 둔 뒤에 목적지를 하나씩 추가하는 방식으로 딕셔너리 자료형을 초기화한다.
그리고 정답으로 알파벳 순서가 앞서는 경로를 return해야 하므로 미리 내림차순으로 sort를 해놓아서 stack으로 pop을 할 때 복잡한 검증과정이 없도록 한다.
for key in graph:
graph[key].sort(reverse=True)첫 출발 경로는 무조건 ICN 이라고 했으니 스택의 맨 앞에 ICN을 넣은 이후 시작을 해보자. 스택의 맨 끝에 있는 요소를 가져와서 그래프 안에 존재하는지, 존재하지 않는지 확인을 하고, 만약 존재한다면 다음 도착지로 존재하는 친구를 뽑아 스택에 추가해준다. 이를 반복하게 된다면 ICN에서 출발하여 모든 도착지를 조회할 수 있을 것이다 (문제 조건에서 경로는 무조건 존재한다고 보장해주었기 때문이다)
while len(stack) > 0:
src = stack[-1]
if graph[src] and len(graph) > 0:
stack.append(graph[src].pop())
else:
answer.append(stack.pop())마지막으로 스택에서 값을 뽑아 넣은 것이니 배열을 뒤집어 주어야 한다.
그럼 원하는 정답으로 결과를 얻을 수 있게 된다.
