주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다.
항상 "ICN" 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
- 모든 공항은 알파벳 대문자 3글자로 이루어집니다.
- 주어진 공항 수는 3개 이상 10,000개 이하입니다.
- tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
- 주어진 항공권은 모두 사용해야 합니다.
- 만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
- 모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
import java.util.*;
class Solution {
static int[][] route;
static List<String> list = new ArrayList<>();
static int N;
static List<String> result = new ArrayList<>();
static List<List<String>> perm = new ArrayList<>();
static String[] answer = {};
public String[] solution(String[][] tickets) {
// 출발지 고정 : ICN(0)
// 방향 그래프, 완전 탐색
// bfs, dfs 둘다 상관없을 듯?
// 공항 갯수 구하기
list.add("ICN"); // ICN은 무조건 0번에서 시작.
for(String[] ticket : tickets){
if(!list.contains(ticket[0])) list.add(ticket[0]);
if(!list.contains(ticket[1])) list.add(ticket[1]);
}
Collections.sort(list);
// 공항 경로 저장.
N = list.size();
route = new int[N][N];
for(int i = 0; i < tickets.length; i++){
String start = tickets[i][0];
String end = tickets[i][1];
int x = list.indexOf(start);
int y = list.indexOf(end);
route[x][y] += 1;
}
for(int i = 0; i < route.length; i++){
int[] r = route[i];
}
int now = list.indexOf("ICN");
result.add("ICN");
dfs(0, now, tickets);
answer = perm.get(0).toArray(new String[perm.get(0).size()]);
return answer;
}
private void dfs(int depth, int now, String[][] tickets){
if(depth == tickets.length){
List<String> li = new ArrayList<>();
for(String str: result){
li.add(str);
}
perm.add(li);
return;
}
for(int i = 0; i < N; i++){
if(route[now][i] > 0){
route[now][i] -= 1;
result.add(list.get(i));
dfs(depth+1, i, tickets);
route[now][i] += 1;
result.remove(result.size()-1);
}
}
}
}