231227 여행경로

private ArrayList<String> visitRoute;
private boolean[] visited;

public String[] solution(String[][] tickets) {
	visitRoute = new ArrayList<>();
	visited = new boolean[tickets.length];
	dfs("ICN", "ICN", tickets, 0);
	Collections.sort(visitRoute);
	return visitRoute.get(0).split(" ");
}

private void dfs(String start, String route, String[][] tickets, int cnt) {
	if (cnt == tickets.length) {
		visitRoute.add(route);
		return;
	}

	for (int i = 0; i < tickets.length; i++) {
		if (start.equals(tickets[i][0]) && !visited[i]) {
			visited[i] = true;
			dfs(tickets[i][1], route + " " + tickets[i][1], tickets, cnt + 1);
			visited[i] = false;
		}
	}
}

출처:https://school.programmers.co.kr/learn/courses/30/lessons/43164