> 문제
문제 : [여행 경로]
> 문제풀이
문제 조건을 잘 보아야 한다.
주어진 티켓(항공권)을 모두 소진 해야하는 조건을 염두해두고 풀었다.
탐색은 DFS 활용.
모두 탐색했을 때, 경로가 2개 이상이라면 알파벳 순서가 앞서는 경로를 Return 해야한다. ( TreeSet 사용 )
소스는 다음과 같다.
import java.util.*;
class Solution {
static Map<String, Map<String, Integer>> routes;
static public String[] solution(String[][] tickets) {
list = new ArrayList<>();
routes = new TreeMap<>();
int cnt = tickets.length;
String a,b;
for(int i=0; i<tickets.length; i++){
a = tickets[i][0];
b = tickets[i][1];
if(routes.get(a) == null) routes.put(a, new TreeMap<>());
if(routes.get(a).get(b) == null) routes.get(a).put(b, 0);
routes.get(a).put(b, routes.get(a).get(b)+1);
}
String start = "ICN";
list.add(start);
dfs(start, 0, cnt);
return answer;
}
static String[] answer;
static boolean flag;
static List<String> list;
static void dfs(String start, int d, int cnt){
if(flag) return;
if(d==cnt) {
answer = new String[list.size()];
for(int i=0; i<list.size(); i++) {
answer[i] = list.get(i);
}
flag = true;
return;
}
if(routes.get(start) == null) return;
Iterator<String> it = routes.get(start).keySet().iterator();
while(it.hasNext()){
String next = it.next();
if(routes.get(start).get(next) <= 0) continue;
routes.get(start).put(next, routes.get(start).get(next)-1);
list.add(next);
dfs(next, d+1, cnt);
routes.get(start).put(next, routes.get(start).get(next)+1);
list.remove(d+1);
}
}
}
문제 출처 : Programmers
PREVIOUS[프로그래머스] Level2 - 소수찾기