プログラマー旅行コース

問題の説明

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

せいげんじょうけん

すべての空港は3文字の大文字で構成されています.
与えられた空港数は3個以上10000個以下である.
チケットの各行[a,b]にはa空港からb空港までの航空券が表示されます.
指定された航空券はすべて使用します.
複数のパスが使用可能な場合は、アルファベット順の先頭にあるパスを返します.
すべての都市へのアクセスは許可されていません.

I/O例

tickets return
[["ICN", "JFK"], ["HND", "IAD"], ["JFK", "HND"]]["ICN", "JFK", "HND", "IAD"]
[["ICN", "SFO"], ["ICN", "ATL"], ["SFO", "ATL"], ["ATL", "ICN"], ["ATL","SFO"]]["ICN", "ATL", "ICN", "SFO", "ATL", "SFO"]
I/O例説明
例1
[ICN,JFK,HND,IADに順次アクセス可能]である.
例2
「ICN」、「SFO」、「ATL」、「ICN」、「ATL」、「SFO」の順にアクセスできますが、「ICN」、「ATL」、「ICN」、「SFO」、「ATL」、「SFO」の順が先です.

解決策

すべての航空券とすべての都市にアクセスするパスの中でアルファベット順により速いパスを出力する問題.
上で指定した航空券はa航空券、b航空券、c航空券の順です.これならまずICN発の航空券の中から1枚選びます
次の都市からの航空券の中から1枚を選びます.
.
.
.
これにより、すべての航空券が使用され、対応するパスに戻ります.
もう一度考えてもいい가지치기即ちbfs使用.条件は現在の都市と出発都市が一致する航空券の中でしか選択できません.使用済みの航空券は使用できません.

初期無効コード

import java.util.*;

class Solution {
    public String[] bfs(String destination, boolean[] used, String[][] tickets)
    {
    	// arrayList로 이루어진 큐 생성
        Queue<List<String>> q = new LinkedList<List<String>>();
        List<String> initList = new ArrayList<String>();
        initList.add("ICN");
        initList.add(destination);
        
        q.offer(initList);
        
        while(!q.isEmpty())
        {   
            List<String> curList = q.poll();
            
            /* 디버깅용 curList를 출력해보기
            System.out.println("curList---------------");
            for (String s : curList)
            	System.out.print(s + " ");
            System.out.println("");
            */
            
            int length = curList.size();
            
            // 모든 항공권 사용시 arrayList를 배열로 변환하여 리턴
            if (length-1 == tickets.length)
            {
                return curList.stream().toArray(String[]::new);
            }
            
            // 모든 항공권 방문하며 현재 장소와 출발지가 일치하고 아직 사용하지 않은 항공권일 경우 사용
            for (int i = 0; i < tickets.length; i++)
            {
                if (curList.get(length-1).equals(tickets[i][0]) && !used[i])
                {   
                    used[i] = true;
                    
                    List<String> nextList = curList;
                    nextList.add(tickets[i][1]);
                    q.offer(nextList);
                }
            }
        }
        String[] tmp = {"hi"};
        return tmp;
    }
    
    // 알파벳 순으로 temp가 더 빠르면 true
    public boolean chk(String[] answer, String[] temp)
    {
        for (int i = 1; i < answer.length; i++)
        {
            if (answer[i].compareTo(temp[i]) < 0)
                return false;
            else if (answer[i].compareTo(temp[i]) > 0)
                return true;
        }
        return false;
    }
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        boolean[] used = new boolean[tickets.length];
        
        String[] temp;
        
        for (int i = 0; i < tickets.length; i++)
        {
            // 출발지가 인천인 항공권 중에서 출발 항공권 고르기 
            if ("ICN".equals(tickets[i][0]))
            {
            	// 항공권 사용 표시 후 bfs 돌리기
                used[i] = true;
                temp = bfs(tickets[i][1], used, tickets);
                
                // 처음이면 bfs에서 구한 경로 answer에 대입
                if (answer.length == 0)
                {
                    answer = temp;
                }
                // 아니면 chk 함수로 알파벳 순으로 더 빠른 것 선택
                else if (chk(answer, temp))
                {
                    answer = temp;
                }
                // 방문 배열 초기화
                Arrays.fill(used, false);
            }
        }
        
        return answer;
    }
}

ただし、bfs変換時にcurlListを出力すると

上図のようにICN、SFOを同時に追加する現象がよく見られます.
bfsが正しく適用されるなら
ICN SFO ATL ICN
ICN SFO ATL SFO
このように単独でキューに入るべきです.

最初の問題はcurlListの長さを長さという変数に入れて管理していないことです。この間の変数値に不一致が発生しました。

if (curList.get(curList.size()-1).equals(tickets[i][0]) && !used[i])

したがって、最後の要素を取得するコード部分は、上記のように変更されました.

2.2つ目の問題は、curlListの浅いコピーによりコンテンツ以外のアドレスがコピーされ、正常に動作しないという問題である。

// 얕은 복사
List<String> nextList = curList;

// 깊은 복사
List<String> nextList = new ArrayList<String>();
for (String s : curList)
	nextList.add(s);

2番目の質問

しかし、上記のように、交換後もテストケースに合格できませんでした.その後、デバッグを行い、その原因を以下にまとめます.

全ての航空券を使用しているかチェックしていない
->アクセスシーケンスが作成され、すべてアクセスされているかどうかを確認します.
しかし、ここには新しい問題が発生しました.私はbfsで実装しているので、アクセスの有無をチェックすると、最初のパスチェックのアクセスと2番目のパスチェックのアクセスが一致しません.

最終的にdfsで実現すべきという結論が得られた.

dfsに置換

全部拭いて交換しました.😓

import java.util.*;

class Solution {
    List<String> answers = new ArrayList<String>();
    boolean[] used;
    
    public void dfs(int cnt, String[][] tickets, String route, String cur)
    {
        if (cnt == tickets.length)
        {
            answers.add(route);
            return;
        }
        
        for (int i = 0; i < tickets.length; i++)
        {
            if (cur.equals(tickets[i][0]) && !used[i])
            {
                used[i] = true;
                dfs(cnt+1, tickets, route + " " + tickets[i][1], tickets[i][1]);
                used[i] = false;
            }
        }
    }
    
    public String[] solution(String[][] tickets) {
        String[] answer = {};
        used = new boolean[tickets.length];
            
        dfs(0, tickets, "ICN", "ICN");
        
        Collections.sort(answers);
        answer = answers.get(0).split(" ");
        return answer;
    }
}

シングルラインサマリー

あるオブジェクトの特性を変数に入れないで、その時にしましょう.情報が一致しない可能性があります.

枝切り方式中경로를 구해야 하는 문제->DFS