プログラマ深度/幅優先ナビゲーション(DFS/BFS)-トラベルパス
https://programmers.co.kr/learn/courses/30/lessons/43164
問題の説明
与えられたすべての航空券を利用して旅行ルートを作りたいです.いつも「ICN」空港から
航空券情報を含む2次元配列航空券をパラメータとして指定する場合は、アクセスした空港経路をレイアウトに入れて返します.
せいげんじょうけん
に答える def dfs(tickets, answer, history, visit, frm, depth):
history += frm + ','
if depth == len(tickets):
answer.append(history[:])
for i in range(len(tickets)):
if tickets[i][0] == frm and visit[i] == 0:
visit[i] = 1
dfs(tickets, answer, history[:], visit, tickets[i][1], depth+1)
visit[i] = 0
def solution(tickets):
answer = []
visit = [0]*len(tickets)
dfs(tickets, answer, '', visit, "ICN", 0)
answer.sort()
answer = answer[0].split(',')[:-1]
return answer
DFSで解読した.
def dfs(tickets, answer, history, visit, frm, depth):
history += frm + ','
if depth == len(tickets):
answer.append(history[:])
for i in range(len(tickets)):
if tickets[i][0] == frm and visit[i] == 0:
visit[i] = 1
dfs(tickets, answer, history[:], visit, tickets[i][1], depth+1)
visit[i] = 0
def solution(tickets):
answer = []
visit = [0]*len(tickets)
dfs(tickets, answer, '', visit, "ICN", 0)
answer.sort()
answer = answer[0].split(',')[:-1]
return answer만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.この条件のためhistoryに文字列を追加しました.リストされた履歴リストはソートされ、一番前のリストのみがリストに変換されて返されます.
Reference
この問題について(プログラマ深度/幅優先ナビゲーション(DFS/BFS)-トラベルパス), 我々は、より多くの情報をここで見つけました https://velog.io/@whanhee97/프로그래머스-깊이너비-우선-탐색DFSBFS-여행경로テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol