「旅行コース」の質問に答える
9208 ワード
序文
今日プログラマーは「旅行ルート」という質問に答えてみました.この問題は分類上DFS/BFSに属する.今、問題を解くときに、この問題をどのようなアルゴリズムで解くべきかを知ることができますが、高得点kitを解いた後、できるだけ知らないうちに行う必要があります.どんなアルゴリズムを使うべきかを知ることから、大きなヒントだと思います.
しかもDFSで解決しました.BFSで問題を解く練習もしなければならないので、今週末は必ず行います.
ソースコード
変数リスト解答-正解を格納する変数 RouteList—可能なすべてのパスを格納する配列 再帰関数を迂回し、routeListにすべてのトラベル可能なパスを格納します.
function travel
この関数を実装し始めたばかりの頃,パラメータとして伝達するものを考慮した.チケットを1枚持っていくか、今の目的地だけ持っていくかをずっと考えていましたが、最後に今までのパスを持っていくのが私にとって一番気持ちがいいことにしました.実際、あなたが何を持っていても、自分の好きなように実現すれば、成功すればいいのです.
パラメータの説明route-旅行途中に到着するルートの並び TicketIndexを使用-使用済チケットのインデックス値を格納する配列 cnt-旅行回数 まず,脱出条件として,旅行回数が票数に等しいときに戻るように設定した.
そして、それまで旅行中に作成したルートはrouteListに保存されていた.
そして、現在のルートの最後を基準に、行ける旅行先を探します.可能であれば、travel()関数を無条件に再再帰的に呼び出す.これで、脱出条件に達するまで、次の目的地に向かうことができます.
その後travel関数が終了すると、routeListには到達可能なすべての旅行経路が含まれ、アルファベット順に一番前の経路を答えに入れて戻せばよい.
ポスト
昨日同じタイプの問題をしたせいか、早い時間で解決したようです.明日から新しいタイプのアルゴリズムの問題を解くつもりです.今日のようにうまくいきたいです.
今日プログラマーは「旅行ルート」という質問に答えてみました.この問題は分類上DFS/BFSに属する.今、問題を解くときに、この問題をどのようなアルゴリズムで解くべきかを知ることができますが、高得点kitを解いた後、できるだけ知らないうちに行う必要があります.どんなアルゴリズムを使うべきかを知ることから、大きなヒントだと思います.
しかもDFSで解決しました.BFSで問題を解く練習もしなければならないので、今週末は必ず行います.
ソースコード
function solution(tickets) {
let answer = 0;
const routeList = []; // 가능한 모든 경로를 저장할 리스트
travel(['ICN'], [], 0); // 처음 출발은 무조건 ICN이다.
// 가능한 모든 경로 중에서 알파벳 순으로 정렬했을 때, 첫 번째가 정답
answer = routeList.sort((a, b) => {
for (let i = 1; i < a.length; i++) {
if (a[i] === b[i]) continue;
// 공항이 같으면 다음 공항을 비교해야 한다
else {
if (a[i] < b[i]) return -1;
else if (a[i] > b[i]) return 1;
}
}
return 0;
})[0];
return answer;
function travel(route, usedTicketIndex, cnt) {
// 종료 조건: 모든 티켓을 다 쓴 그 순간이 종료되야하는 시점
if (cnt === tickets.length) {
routeList.push(route);
return;
}
// 티켓들을 쭉 보면서
for (let i = 0; i < tickets.length; i++) {
// 쓴 티켓은 제외하고
if (usedTicketIndex.includes(i)) continue;
// 현재 있는 곳에서 갈 수 있는 모든 공항을 travel 해준다.
if (tickets[i][0] === route[route.length - 1]) {
travel([...route, tickets[i][1]], [...usedTicketIndex, i], cnt + 1);
}
}
return;
}
}
説明する変数リスト
function travel
この関数を実装し始めたばかりの頃,パラメータとして伝達するものを考慮した.チケットを1枚持っていくか、今の目的地だけ持っていくかをずっと考えていましたが、最後に今までのパスを持っていくのが私にとって一番気持ちがいいことにしました.実際、あなたが何を持っていても、自分の好きなように実現すれば、成功すればいいのです.
パラメータの説明
そして、それまで旅行中に作成したルートはrouteListに保存されていた.
そして、現在のルートの最後を基準に、行ける旅行先を探します.可能であれば、travel()関数を無条件に再再帰的に呼び出す.これで、脱出条件に達するまで、次の目的地に向かうことができます.
その後travel関数が終了すると、routeListには到達可能なすべての旅行経路が含まれ、アルファベット順に一番前の経路を答えに入れて戻せばよい.
ポスト
昨日同じタイプの問題をしたせいか、早い時間で解決したようです.明日から新しいタイプのアルゴリズムの問題を解くつもりです.今日のようにうまくいきたいです.
Reference
この問題について(「旅行コース」の質問に答える), 我々は、より多くの情報をここで見つけました https://velog.io/@munyohan/여행경로-문제-풀이テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol