リンク

旅行コース

問題の説明

与えられたすべての航空券を利用して旅行ルートを作りたいです.いつも「ICN」空港から
航空券情報を含む2次元配列航空券をパラメータとして指定する場合は、アクセスした空港経路をレイアウトに入れて返します.

せいげんじょうけん

すべての空港はアルファベットの大文字の3文字で構成されています.

所定の空港数は3つ以上10000個以下である.

切符の各行[a,b]は、a空港からb空港までの航空券があることを示す.

の航空券はすべて使用します.

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

すべての都市へのアクセスは許可されていません.

に答える

答案用紙が見えました…!
回答用紙の場合は、アクセスしたすべてのパスをリストに入れ、ソートしてリストします.get(0).split(""")で順番に入れるだけで...!実は簡単です...

Code

import java.util.*;
class Solution {
    static ArrayList<String> list=new ArrayList<String>();
    public String[] solution(String[][] tickets) {
        boolean visited[]=new boolean[tickets.length];
        String[] answer = {};
        DFS("ICN","ICN",0,visited, tickets);
        
        Collections.sort(list);
        answer=list.get(0).split(" ");
        return answer;
    }
    
    public static void DFS(String start, String result, int idx, boolean visited[], String tickets[][])
    {
        if(idx==tickets.length)
        {
            list.add(result);
            return ;
        }
        
        for(int i=0; i<tickets.length; i++)
        {
            if(!visited[i] && start.equals(tickets[i][0]))
            {
                visited[i]=true;
                DFS(tickets[i][1], result+" "+tickets[i][1], idx+1, visited, tickets);
                visited[i]=false;
            }
        }
    }
}