[TIL]プログラマー旅行経路:DFS/BFS

function solution(tickets) {
    
    // 출발지, 도착지 정보 담는 객체 생성
    const plane = {};
    
    for (const t of tickets) {
        if (!plane[t[0]]) {
            plane[t[0]] = [t[1]]; 
        } else {
            plane[t[0]].push(t[1])
        }
    }
    
    // 도착지 내림차순 정렬 .sort((a, b) => b - a); 왜 안 됨?
    for (const p in plane) plane[p].sort().reverse();
    
    // 여행 경로 정하기, 첫 출발지는 무조건 ICN
    const route = ['ICN'];
    // 출발지가 포함이기 때문에 가지고 있는 항공권보다 경로 횟수는 1회 높다
    const count = tickets.length + 1
    
    while(route.length < count){
        for (const country in plane){
            if (country === route[route.length-1] && plane[country]){
                route.push(plane[country].pop())
            }
        }
    }
    
    return route;
}

この問題を解くのは遅くなりますが、今でなければ余裕がないかもしれませんので、まだ分からない問題を理解するために、今から1週間目の実習問題を解答し始めました.最初はグラフで解いたので、テスト例が合格したと思ってもいいですが、採点したところ、4つのケースのうち1つしか合格しておらず、他のケースはタイムアウトしていました.
何が原因なのか、グーグルゲームをたくさん試してみましたが、このコードには例外はありません.
問題の1つの条件は

可能なパスが2つ以上ある場合は、アルファベット順にリードするパスを返します.

これは、[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]を入力値として受け取った場合、["ICN", "SFO", "ATL", "ICN", "ATL", "SFO"]の順でアクセスすることもできますが、["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]はアルファベット順でリードしているので、アルファベット順で処理します.
ただし例外に戻ると、上のコードは[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ICN"]]であり、これを入力値とすると、出発地、到着地を入力してアルファベット順に並べ替えるので、ICN以降は当然SFOとATLのうちATLに先に入る.ATLに到着した後は、次の目的地まで行ける航空券がなかったので、これ以上行くことができず、そこで繰り返し文が終わらず、引き返し続けました.したがって,このコードは終了していないためタイムアウトが発生するため,DFSを再帰的に解放する必要がある.
ブログリンクを参照

📝 BFS / DFS

BFS Breadth First Search:まず幅をブラウズ

キュー(FIFO)を使用して実装することができる.

の始点に近い頂点から順にナビゲートします.

例問題)プログラマ:最も遠いノード
この問題はグラフとBFSで解くことができる.

DFS Depth First Search:深度優先ナビゲーション

スタック(LIFO)を使用して実装することができる.

の起点から、最も深い頂点を探索し、次の頂点を同様に探索する.

例問題)プログラマー:旅行コース2