문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 ICN 공항에서 출발합니다.
항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.
제한사항
모든 공항은 알파벳 대문자 3글자로 이루어집니다.
주어진 공항 수는 3개 이상 10,000개 이하입니다.
tickets의 각 행 [a, b]는 a 공항에서 b 공항으로 가는 항공권이 있다는 의미입니다.
주어진 항공권은 모두 사용해야 합니다.
만일 가능한 경로가 2개 이상일 경우 알파벳 순서가 앞서는 경로를 return 합니다.
모든 도시를 방문할 수 없는 경우는 주어지지 않습니다.
입출력 예
tickets return
[[ICN, JFK], [HND, IAD], [JFK, HND]][ICN, JFK, HND, IAD]
[[ICN, SFO], [ICN, ATL], [SFO, ATL], [ATL, ICN], [ATL,SFO]][ICN, ATL, ICN, SFO, ATL, SFO]
입출력 예 설명
예제 #1
[ICN, JFK, HND, IAD] 순으로 방문할 수 있습니다.
예제 #2
[ICN, SFO, ATL, ICN, ATL, SFO] 순으로 방문할 수도 있지만 [ICN, ATL, ICN, SFO, ATL, SFO] 가 알파벳 순으로 앞섭니다.
Code
import java.util.*;
class Solution {
boolean[] visited;
ArrayList<String> answers;
public String[] solution(String[][] tickets) {
visited = new boolean[tickets.length];
answers = new ArrayList<String>();
int count =0;
dfs(count,"ICN","ICN",tickets);
Collections.sort(answers); //alphabet 순서가 빠른대로 정렬
String[] answer = answers.get(0).split(" ");
return answer;
}
public void dfs(int count, String present, String answer, String[][] tickets){
if(count == tickets.length) {
answers.add(answer);
return;
}
for(int i=0; i<tickets.length; i++){
// 방문한 적 없는 공항이고 이전 노드의 도착지와 현재 탐색 중인 노드의 출발지가 같다면?
if(!visited[i] && tickets[i][0].equals(present)){
visited[i] = true;
dfs(count+1, tickets[i][1], answer+" "+tickets[i][1], tickets);
visited[i] = false;
}
}
}
}풀이
- 흔한 dfs의 풀이처럼 해당 노드의 방문 기록을 기록하기 위한 boolean 배열을 만들어준다.
- alphabet 우선 순위로 뽑아내라 그래서 처음부터 정렬해서 보낼까? 생각해봤는데 2차원 배열에서 String값 정렬하는게 까다로웠다..👀
- Collections를 이용해서 나온 결과 값만 정렬하고 리턴한다.
- dfs를 이용하여 전체 방문 공항 수와 일치할때까지 count를 올린다.
- 그 과정에서 방문한 적 없는 공항이고 이전 노드의 도착지와 현재 탐색 중인 노드의 출발지가 일치하는 곳을 찾아서 방문 처리하고 count올리고 현재 도착지를 이전 노드 도착지로 바꾸고 answer 값을 갱신시키고 또 dfs를 돌린다...
📝
사실, 다른 분의 풀이를 참고했다. 거의 다 참고했다..
dfs에 많이 익숙해졌다 생각했는데 개뿔..🤯
정말.. 매번 생각해내는데 몇시간 걸리고 실패를 반복만 하다가 끝난다..후
머리속에서 그럴듯한 경로가 떠오를때까지 쥐날때까지 생각해야 힌트라도 살짝 나오는 정도가 나에겐 dfs인 것 같다..
