[프로그래머스]DFS:여행경로(java)

문제보러가기

코딩테스트 연습 - 여행경로

이문제는 경로가 여러개 나올수 있다는 점과 그럴 경우 알파벳 순서가 앞서는 경로를 답으로 택하는것만 주의하면 되는 문제였다. 나는 경로가 여러개 나올때 계속 같은경로가 여러번 저장되길래 삽질을 좀 했다..;; array의 주소값으로 참조함을 잊지말자 ㅎ.. copy사용을 생각하자...ㅎ

 

 

 

 

문제풀이

-"ICN"으로 시작하는걸 start

-ticket[i][1]이 다음 start가 된다.

-모든경우를 탐색한 후 list에 저장된 경로 중 알파벳순으로 sorting

 

 

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class Solution {
	
    //여행경로를 담을 list
	static ArrayList<String[]> list = new ArrayList<>();
	public static void main(String[] args) {

		String[][] tickets ={ {"ICN", "SFO"}, {"ICN", "ATL"},{"SFO", "ATL"}, {"ATL", "ICN"}, {"ATL", "SFO"}};
		
		String start = "ICN";
		String[] answer = new String[tickets.length+1];
 		boolean[] visited = new boolean[tickets.length+1];
		dfs(visited,start,tickets,0,answer);

		//경로가 2개이상일때부터 알파벳 순으로 정렬
		if(list.size()>1){
			Collections.sort(list,new Comparator<String[]>(){

				@Override
				public int compare(String[] o1, String[] o2) {
					int compare;
					String s1="";
					String s2="";
					for(int i=0;i<o1.length;i++){
						s1+=o1[i];
						s2+=o2[i];
					}
					return s1.compareTo(s2);
				}
				
			});
		}
		answer = list.get(0);

	}
	public static void dfs(boolean[] visited, String start,String[][] tickets,int index,String[] answer){
		
        //전체 티켓을 다 사용하면 list에 add
        //value값을 copy해서 넣어줌.
		if(index == tickets.length){
			String[] copy = new String[index+1];
			for(int i=0;i<answer.length;i++){
				copy[i] = answer[i];
			}
			list.add(copy);
			return;
		}
		
        //전체 티켓을 다 사용하지 않았다면 start 티켓을 찾아 다시탐색
		for(int i=0;i<tickets.length;i++){
			if(start.equals(tickets[i][0])&&!visited[i]){
				visited[i]=true;
				answer[index]=start;
				answer[index+1] = tickets[i][1];
				dfs(visited,tickets[i][1],tickets,index+1,answer);
				visited[i]=false;
			}
		}
		return;
		
	}


}