[Programmers] 여행 경로 - 깊이/너비 우선 탐색(DFS/BFS)

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

// 여행 경로 - 깊이/너비 우선 탐색(DFS/BFS)
public class TravelRoute {
	
	/*
	 *  Test Case 1)
	 *  INPUT : [["ICN", "BOO"], ["ICN", "COO"], ["COO", "DOO"], ["DOO", "COO"], ["BOO", "DOO"], ["DOO", "BOO"], ["BOO", "ICN"], ["COO", "BOO"]]
	 *  =>
	 *  OUTPUT : ["ICN", "BOO", "DOO", "BOO", "ICN", "COO", "DOO", "COO", "BOO"]
	 */
	
	private static ArrayList<String> list = new ArrayList<>();
	private static String route = "";
	private static boolean[] visit;

	public String[] solution(String[][] tickets) {
		for (int i = 0; i < tickets.length; i++) {
			visit = new boolean[tickets.length];
			if (tickets[i][0].equals("ICN")) {
				route = tickets[i][0] + " ";
				visit[i] = true;
				dfs(tickets, tickets[i][1], 1);
			}
		}
		Collections.sort(list);
		return list.get(0).split(" ");
	}

	private void dfs(String[][] tickets, String arrival, int cnt) {
		route += arrival + " ";
		if (cnt == tickets.length) { // 티켓을 모두 사용했을 때만, list에 삽입
			list.add(route);
			return;
		}
		for (int i = 0; i < tickets.length; i++) {
			if (tickets[i][0].equals(arrival) && !visit[i]) {
				visit[i] = true;
				dfs(tickets, tickets[i][1], cnt + 1);
				visit[i] = false; // 모든 경로를 계산하기 위해 현재 visit를 다시 false 선언
				route = route.substring(0, route.length() - 4); // 모든 경로를 계산하기 위해 route 문자열을 뒤에서부터 4글자 만큼 제거 ("ICN ".length() == 4)
			}
		}
	}
}