[출처] : https://programmers.co.kr
문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입출력 예
입출력 예 설명
예제 #1
["ICN", "JFK", "HND", "IAD"] 순으로 방문할 수 있습니다.
예제 #2
["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"] 순으로 방문할 수도 있지만 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 가 알파벳 순으로 앞섭니다.
접근 및 코드
각 공항을 노드로 생각하고 주어진 비행기 표를 간선의 정보라고 생각하면 그래프 탐색이라고 생각할 수 있다.
경로를 구하는 문제라서 DFS로 구하는 것이 좋을것 같아서 DFS로 풀었다.
(A->B로 가는것이 있으면 바로 이어서 B->C 이런식으로 깊이 우선으로 찾기 위해)
우선 딕셔너리를 이용해서 그래프를 구성했다.
이때 defaultdict를 이용해서 value 를 리스트로 초기화 해두었다.(이렇게 하면 훨씬 편함)
{"ICN": ["자식노드1","자식노드2"]}
이와 같이 그래프정보를 저장했다.
그리고 이 자식노드 리스트를 전부 역방향으로 정렬 했는데, 이는 dfs로 탐색할것이기 때문이다.
아래 dfs그림을 보자
[출처] : https://velog.io/@vagabondms/DFS-vs-BFS
dfs는 스택을 이용하기 때문에 리스트상으로 뒤쪽에 있는 것이 먼저 나오게 된다.
문제를 보면, 방문경로가 여러개이면, 알파벳 순으로 앞선 것을 경로상 먼저나오게 해야된다
예를 들면 ["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"]이러한 경로와 ["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"] 이 두가지 경로가 있다하면 후자가 알파벳상으로 앞서기 때문에 이것을 골라야한다.
그렇기 때문에 탐색과정에서 애초에 알파벳순서상 먼저 앞서는 것을 뽑기 위해 역순으로 정렬한 것이다.
이 상태로 dfs로 경로를 구한다.
일반적으로 dfs를 할때 스택에서 하나씩 pop하는데, 이 경우에는 해당 위치에서 출발하는 티켓이 여러장일수 있기 때문에 그 경우를 확인해야 한다.
따라서 스택에서 pop하는것이 아닌 마지막 값을 조회하고, 해당위치에서 출발하는 티켓이 없거나, 티켓을 다 사용했다면(자식노드가 없다면), 더 이상 진행할수 없다는 뜻이므로 이를 경로에 넣어주면 된다.
만약 다음 위치로 가는 표가 있으면 다음 탐색을 위해서 스택에 넣어주면 된다.
이렇게 해서 경로를 구하면 되는데, 지금 보면 경로를 저장하는 리스트에 경로상 뒤쪽 값이 리스트의 맨앞에 저장되어있다.
위에 올린 DFS 그림을 보면 6-5-2-4-3-1-0 이런식으로 역순으로 저장이 된것이다.
따라서 경로를 reverse() 를 이용해서 경로를 거꾸로 뒤집어 주어야 한다.
다음은 코드이다.
from collections import defaultdict
def dfs(start_node, graph):
path = list()
need_visited = list()
need_visited.append(start_node)
while need_visited:
current_node = need_visited[-1]
#해당 위치에서 출발하는 티켓이 없던가, 티켓을 다사용한 경우(자식노드가 없는 경우)
if current_node not in graph or len(graph[current_node]) == 0:
#경로에 추가
path.append(need_visited.pop())
#다음 위치로 가는 표가 있으면
else:
need_visited.append(graph[current_node].pop())
return path
def solution(tickets):
#그래프 만들기
graph = defaultdict(list)
for i in tickets:
graph[i[0]].append(i[1])
#알파벳순으로 빠른 값으로 출력하기 위해 자식노드들 정렬
for j in graph.keys():
graph[j].sort(reverse=True)
answer = dfs("ICN",graph)
#거꾸로 경로를 구했기 때문에 한번 뒤집어주어야됨
answer.reverse()
return answer결과
