문제 설명
주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "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"]가 알파벳 순으로 앞섭니다.
풀이
문제 풀 때 ticket를 맵에다 저장해서 ticket배열의 [0][0] 원소를 맵에서 찾아서 경로 이동 -> 반복하는 흐름의 코드를 짰는데
[["ICN", "AOO"], ["AOO", "BOO"], ["BOO", "COO"], ["COO", "DOO"], ["DOO", "EOO"], ["EOO", "DOO"], ["DOO", "COO"], ["COO", "BOO"], ["BOO", "AOO"]]
반례에서 막혔다. 이전에 갔던 여행지를 다시 가기 위해 visited 맵을 만들어서 무한루프를 막았지만 ["EOO", "DOO"]와 같이 이미 방문했던 여행지를 다시 방문하는 문제와 value리스트에서 방문한 여행지를 나중에 다시 방문하는 코드를 짜다가 막혀서 다 지우고 계속 고민했다.
그 결과 힌트를 찾아봤다.
일단 접근부터 어렵게 갔었다. 맵으로 저장하지 말고 티켓 하나하나에 대해 사용 여부와 이동 경로를 파악했으면 훨씬 간단하게 짤 수 있었다. 이렇게 짜게 된다면 티켓들로 만들 수 있는 다수의 여행경로가 나오는데 그중 알파벳 순서로 먼저 있는 것을 출력하면 정답인 것이다.
단계는 3단계로 나눌 수 있다.
- dfs탐색
- 탐색 횟수가 티켓 개수와 동일하면 루트를 저장
- 루트 리스트를 오름차순으로 정렬 후 첫 루트를 출력한다
일단 변수가 2개 필요하다.
val isVisited = BooleanArray(tickets.size) //티켓 사용여부
val allRoute = ArrayList<String>() //모든 경로를 저장이제 티겟 개수에 만큼 탐색하면 된다.
fun dfs(tickets: Array<Array<String>>, start: String, route: String, cnt: Int, isVisited: BooleanArray, allRoute: ArrayList<String>){
if(tickets.size == cnt) {
allRoute.add(route)
return
}
for (i in tickets.indices){
if(start == tickets[i][0] && !isVisited[i]) {
isVisited[i] = true
dfs(tickets, tickets[i][1], route + " " + tickets[i][1], cnt + 1, isVisited, allRoute)
isVisited[i] = false
}
}
}마지막으로 정렬해주고 출력하면 된다
allRoute.sort()
answer = allRoute[0].split(" ").toTypedArray()
return answer이렇게 간단한걸.... 혼자 꼬아서 1시간 30분 동안 고생했다.
마지막으로 전체 코드를 올리고 마무리하겠다.
class Solution {
fun solution(tickets: Array<Array<String>>): Array<String> {
var answer = arrayOf<String>()
val isVisited = BooleanArray(tickets.size) //티켓 사용여부
val allRoute = ArrayList<String>() //모든 경로를 저장
dfs(tickets, "ICN", "ICN", 0, isVisited, allRoute)
allRoute.sort()
answer = allRoute[0].split(" ").toTypedArray()
return answer
}
fun dfs(tickets: Array<Array<String>>, start: String, route: String, cnt: Int, isVisited: BooleanArray, allRoute: ArrayList<String>){
if(tickets.size == cnt) {
allRoute.add(route)
return
}
for (i in tickets.indices){
if(start == tickets[i][0] && !isVisited[i]) {
isVisited[i] = true
dfs(tickets, tickets[i][1], route + " " + tickets[i][1], cnt + 1, isVisited, allRoute)
isVisited[i] = false
}
}
}
}