[Java]Programmersトラベルパス(DFS)

Programmers Lv 3トラベルパス

深さ/幅優先ナビゲーション(DFS/BFS)

level3

🔍 問題の説明

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

せいげんじょうけん

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

💡 に答える

これはかなり時間がかかる問題です.
長い間BFSで解決してみましたが、ずっと解決していません.
DFSの使用(論理類似)
この問題のポイントは경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.です.
これはString[]型ArrayList routesを用いて実現した.
(他の方法も試したことがあるが(map,stack)、成功しなかった...)
DFSに移動してパスを保存し、パスが完了したらroutesに追加します.
グローバル変数は次のとおりです.int LEN:航空券リストの長さboolean[] visited:航空券が使用されているかどうかを確認するためのブール型アレイArrayList<String[]> routes:すべてのパスを保存するリスト
DFSメソッドのパラメータは次のとおりです.int idx:パスidxString from:出発地String[][] tickets:航空券リストString[] route:旅行コース
DFSメソッドでチケットが提供されている場合、
つまり、チケットがfromと同じなら、
使用チケット(アクセス済小切手)
経路指定のためのチケットの到着地を保存し、その到着地を出発地として他のチケットにナビゲートする.
上記の手順を繰り返し、すべてのチケットを使用する場合(idx=LEN)
[グローバルリストルーティング]で、現在アクセスしているルーティングスキームを追加します.

private void dfs(int idx, String from, String[][] tickets, String[] route) {
	if(idx==LEN) { //모든 티켓 사용 하여 경로를 다 찾았다면
			
		String[] tmp = new String[LEN+1];
		for(int i = 0; i<= LEN ; i++) {
			tmp[i] = route[i];
		}
			
		routes.add(tmp); //최종 ArrayList에 카피하여 경로 삽입 
		return;
	}
		
	for(int i=0 ; i <tickets.length ; i++) {
		String dept = tickets[i][0];
		String dest = tickets[i][1];
			
		if(visited[i]) continue; //이미 사용한 티켓이라면 continue
		if(from.equals(dept)) {
			//사용 가능한 티켓이다
			visited[i] = true;
			route[idx+1] = dest;
			dfs(idx+1, dest, tickets, route);
			visited[i] = false;
		}
	}
		 
     
		
}

最後にroutes.size()>1の場合は、Comparatorを使用してアルファベット順に並べ替えられます.

Collections.sort(routes, new Comparator<String[]>(){

	@Override
	public int compare(String[] o1, String[] o2) {
					
		String s1 = "";
		String s2 = "";
		for(String s : o1) {
			s1 += s;
		}
		for(String s : o2) {
			s2 += s;
		}
					
		return s1.compareTo(s2);
					
	}
    			
});

次に、問題の要求に従って、アルファベット順にリードするパスを返します.

💡 ソースコード

import java.util.*;

class Solution {
    static int LEN;
	static boolean[] visited;
	static ArrayList<String[]> routes = new ArrayList<>();
	
    public String[] solution(String[][] tickets) {
    	LEN = tickets.length;
    	visited = new boolean[LEN+1]; //방문체크
        
        String[] route = new String[LEN+1]; //경로 담을 배열
 	    route[0] = "ICN"; //항상 "ICN" 공항에서 출발
    	dfs(0, "ICN", tickets, route);
    	// idx  start  ticket리스트, 경로
    	
    	if(routes.size()>1) {
    		//경로가 2개 이상이다? 알파벳 순서대로 정렬
    		
    		Collections.sort(routes, new Comparator<String[]>(){

				@Override
				public int compare(String[] o1, String[] o2) {
					
					String s1 = "";
					String s2 = "";
					for(String s : o1) {
						s1 += s;
					}
					for(String s : o2) {
						s2 += s;
					}
					
					return s1.compareTo(s2);
					
				}
    			
    		});
    	}

        return routes.get(0); //알파벳 순서가 앞서는 경로를 return
    }

	private void dfs(int idx, String from, String[][] tickets, String[] route) {
		if(idx==LEN) { //모든 티켓 사용 하여 경로를 다 찾았다면
			
			String[] tmp = new String[LEN+1];
			for(int i = 0; i<= LEN ; i++) {
				tmp[i] = route[i];
			}
			
			routes.add(tmp); //최종 ArrayList에 카피하여 경로 삽입 
			return;
		}
		
		for(int i=0 ; i <tickets.length ; i++) {
			String dept = tickets[i][0];
			String dest = tickets[i][1];
			
			if(visited[i]) continue; //이미 사용한 티켓이라면 continue
			if(from.equals(dept)) {
				//사용 가능한 티켓이다
				visited[i] = true;
				route[idx+1] = dest;
				dfs(idx+1, dest, tickets, route);
				visited[i] = false;
			}
		}
		 
        return;
		
	}
}