참고
문제해설
문제 로직고민
NOTE
•
그래프의 DFS 탐색을 사용해서, 모든 간선(티켓)을 사용해야 한다.
◦
중복 방문은 허용한다.
◦
Map을 통해 각 공항에서 갈 수 있는 공항을 담은후, 알파벳순으로 정렬한다.
◦
이후에는 DFS를 통해, 티켓을 모두 소모하는 경우가 나올때까지 방문을 반복한다.
◦
방문한 티켓의 경우, 도착지 공항끝에 X 알파벳을 추가하고, 공항글자가 3인경우만 탐색하게 한다.
작성코드
NOTE
import java.util.*;
class Solution {
int ticketNum;
Map<String, List<String>> map;
String[] result;
public String[] solution(String[][] tickets) {
this.ticketNum = tickets.length;
this.map = new HashMap();
for(String[] ticket : tickets){
String s = ticket[0];
String d = ticket[1];
map.putIfAbsent(s, new ArrayList<String>());
map.get(s).add(d);
}
for(Map.Entry<String, List<String>> entry : map.entrySet()){
Collections.sort(entry.getValue());
}
result = new String[ticketNum+1];
dfs(0, "ICN", result);
return result;
}
private void dfs(int step, String s, String[] way){
if(way[ticketNum] != null) return; // 이미 도착한 경우
if(step == ticketNum) {
way[step] = s;
return;
}
List<String> temp = map.get(s);
if (temp == null) return; // 해당 공항에서 갈 수 있는 티켓이 없는경우
way[step] = s;
for(int i=0; i<temp.size(); i++){
String d = temp.get(i);
if(d.length() == 3){
temp.set(i, d + "X"); // 방문한 티켓은 도착지 끝에 X를 붙임
dfs(step + 1, d, way);
temp.set(i, d); // 원상태 복구
}
}
}
}
Java
복사
방문 문자열을 확인하는 로직을 조금 고민했다.
다른사람 풀이
NOTE
import java.util.*;
class Solution {
static boolean[] ch;
static ArrayList<String> route;
public String[] solution(String[][] tickets) {
String[] answer = {};
ch = new boolean[tickets.length];
route = new ArrayList<>();
DFS("ICN", "ICN", tickets, 0);
Collections.sort(route);
answer = route.get(0).split(" ");
return answer;
}
public void DFS(String dpt, String arr, String[][] tickets, int cnt){
if(cnt == tickets.length) {
route.add(arr);
return;
}
for(int i = 0; i < tickets.length; i++) {
if(dpt.equals(tickets[i][0]) && !ch[i]) {
ch[i] = true;
DFS(tickets[i][1], arr + " " + tickets[i][1], tickets, cnt + 1);
ch[i] = false;
}
}
}
}
Java
복사
더 깔끔한 코드