프로그래머스 여행경로

문제 : 프로그래머스 여행경로

https://programmers.co.kr/learn/courses/30/lessons/43164?language=java 

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

 

풀이

① DFS로 모든 경로 목록 구하기

② 알파벳 순서로 정렬 후 가장 앞의 것을 출력

 

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.Stack;

class Solution {
    public static ArrayList<String> routes = new ArrayList<>();
    
	public String[] solution(String[][] tickets) {
		
		String now = "ICN";
		boolean[] used = new boolean[tickets.length];
		Stack<String> route = new Stack<>();
		
		route.add(now);
		dfs(tickets, used, now, route);
		
		Collections.sort(routes);
		
        return routes.get(0).replace("[", "").replace("]", "").split(", ");
    }

	private void dfs(String[][] tickets, boolean[] used, String now, Stack<String> route) {
		
		if(route.size() == tickets.length+1) {
			routes.add(route.toString());		
			return;
		}
		
		
		for(int i = 0; i<tickets.length; i++) {
			if(!used[i] && now.equals(tickets[i][0]) ) {
				used[i] = true;
				route.add(tickets[i][1]);
				dfs(tickets, used, tickets[i][1], route);
				used[i] = false;
				route.pop();
			}
		}
		
	}
}