여행경로
Prov
tickets을 모두 이용하여 여행경로 짜기 가능 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로 선택
Solv
도착지가 다음 노드이고 다음 노드의 알파벳 순서대로 우선순위를 설정해야 하므로 도착지를 기준으로 tickets정렬 DFS나 BFS로 now==tickets[1]인 경우 여행경로 생성 사용한 ticket은 visit으로 체크해서 중복 방지
Check
tickets=[[“ICN”, “SFO”], [“ICN”, “ATL”], [“SFO”, “ATL”], [“ATL”, “ICN”], [“ATL”,”SFO”]]
정렬 후 [[“ICN”, “ATL”], [“SFO”, “ATL”], [“ATL”, “ICN”], [“ICN”, “SFO”], [“ATL”, “SFO”]]
DFS
| depth | ticket |
|---|---|
| 0 | ICN |
| 1 | ATL |
| 2 | ICN |
| 3 | SFO |
| 4 | ATL |
| 5 | SFO |
| 2 | SFO |
| 3 | ATL |
| 4 | ICN |
| 5 | SFO |
| 1 | SFO |
| 2 | ATL |
| 3 | ICN |
| 4 | ATL |
| 5 | SFO |
| 3 | SFO |
BFS
정렬한 tickets를 0부터 인덱싱하여 딕셔너리로 변형
ICN을 포함하는 ticket을 deque 초기값으로 지정
매 반복마다 visit을 초기화
deque에 tickets와 동일한 길이가 입력되면 반환
| deque |
|---|
| [[3], [0, 2], [0, 4]] |
| [[0, 2], [0, 4], [3, 1]] |
| [[0, 4], [3, 1], [0, 2, 3]] |
| [[3, 1], [0, 2, 3], [0, 4, 1]] |
| [[0, 2, 3], [0, 4, 1], [3, 1, 2], [3, 1, 4]] |
| [[0, 4, 1], [3, 1, 2], [3, 1, 4], [0, 2, 3, 1]] |
| [[3, 1, 2], [3, 1, 4], [0, 2, 3, 1], [0, 4, 1, 2]] |
| [[3, 1, 4], [0, 2, 3, 1], [0, 4, 1, 2], [3, 1, 2, 0]] |
| [[0, 2, 3, 1], [0, 4, 1, 2], [3, 1, 2, 0]] |
| [[0, 4, 1, 2], [3, 1, 2, 0],[0, 2, 3, 1, 4]] |
| [[3, 1, 2, 0], [0, 2, 3, 1, 4], [0, 4, 1, 2, 3]] |
| [[0, 2, 3, 1, 4], [0, 4, 1, 2, 3], [3, 1, 2, 0, 4]] |
| [[0, 4, 1, 2, 3], [3, 1, 2, 0, 4]] |
| [[3, 1, 2, 0, 4]] |
| [] |
