문제
분석
Constraints
1. 모든 항공권을 사용해한다.
2. 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 해당 제약 조건으로부터 `
DFS로 풀어야 한다는 것을 유추할 수 있다! (아무생각없이 BFS로 처음 풀었다가 시간 낭비,,)
WHY?
- 이 문제에서 요구하는 '하나의 경로를 완성하는' 방식에 경로를 탐색할 때 한 방향으로 깊이 들어가며 탐색하는 DFS가 더 적합
이 문제는 풀어보길 추천!!!
DFS 코드
import itertools
def solution(tickets):
answer = []
final_depth = len(tickets)+1
graph = {}
visited = {}
all_airport = set(list(itertools.chain(*tickets)))
n_ports = len(all_airport)
#visited = Counter(all_airport)
# 1. empty graph 만들기
for port in all_airport:
graph[port] = []
visited[port] = []
# graph 채우기
for frm, to in tickets:
graph[frm].append(to)
visited[frm].append(0) # 방문x -> 0
for k, v in graph.items():
graph[k] = sorted(v)
def dfs(cur_v, path):
# base case
if len(path) == final_depth:
return path
#print("----\ncur_v: ", cur_v, final)
#for next_v, vst in zip(graph[cur_v], visited[cur_v]):
for idx, next_v in enumerate(graph[cur_v]):
#print("for: ", next_v, visited)
if not visited[cur_v][idx]:
visited[cur_v][idx] = 1
new_path = path + [next_v]
#print("bf dfs: ", next_v)
result = dfs(next_v, new_path)
if result:
return result
visited[cur_v][idx] = 0
path = dfs("ICN", ["ICN"])
return path처음 시행착오: Backtracking
Backtracking을 진행하지 않았음! DFS를 진행하면, 현재 경로에서 더 이상 진행할 수 없을 때 이전 분기점으로 쉽게 돌아갈 수 있는 backtracking을 구현해야한다!!! 따라서, 중요한 점은 dfs() 함수가 return 되면해당 노드의 visited 다시 reset시켜주어야 한다.
ex) 그래프를 어떻게 순회하냐에 따라
hot -> dot -> dog -> log -> cog 순으로 먼저 순회하면 바로 length = 5로 종료!
하지만 hot -> dot -> dog -> cog의 최단거리가 존재!
- 해당 부분의 코드는 아래와 같다.
.
.
.
result = dfs(next_v, new_path)
if result:
return result
############ HERE ############
visited[cur_v][idx] = 0
##############################결과
- Backtracking을 하지 않았을 때에는 NONE!이 반환된다!!
if __name__ == "__main__":
tickets = [["ICN", "A"], ["A", "C"], ["C", "A"], ["A", "B"], ["B", "ICN"]]
a = solution(tickets=tickets)
print(a)['ICN', 'A', 'C', 'A', 'B', 'ICN']
