[DFS/BFS] 여행경로 - Java코드 ★★★

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

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

 

 

문제

 

 

풀이

 

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

class 여행경로 {
/*
테스트 1 〉	통과 (78.43ms, 106MB)
테스트 2 〉	통과 (8.62ms, 81.2MB)
테스트 3 〉	통과 (8.83ms, 79MB)
테스트 4 〉	통과 (9.02ms, 74.9MB)
*/
static ArrayList<String> answer;
	static Boolean [] visited;
	public String[] solution(String[][] tickets) {
		answer = new ArrayList<>();
		visited = new Boolean[tickets.length+1];
		Arrays.fill(visited, false);
		String ans = "ICN ";
		dfs("ICN",tickets,ans,1);
		Collections.sort(answer);
		return answer.get(0).split(" ");
	}
	private static void dfs(String from, String[][] tickets, String ans,int idx) {
		if(idx==tickets.length+1) {
			answer.add(ans);
			return;
		}
		for(int i=0;i<tickets.length;i++) {
			if(!visited[i] && from.equals(tickets[i][0])) {
				visited[i] = true;
				dfs(tickets[i][1], tickets, ans+tickets[i][1]+" ", idx+1);
				visited[i] = false;
			}
		}
	}
}

경로를 반환하는 값이 String[] 배열이지만,

반환전까지 List에 모든 정답 경로를 담았다가, 

알파벳순서로 정렬후 가장 첫번째값을 String 배열로 변환시켜 반환해주었다.