프로그래머스 - 여행경로

문제 설명

주어진 항공권을 모두 이용하여 여행경로를 짜려고 합니다. 항상 "ICN" 공항에서 출발합니다.

항공권 정보가 담긴 2차원 배열 tickets가 매개변수로 주어질 때, 방문하는 공항 경로를 배열에 담아 return 하도록 solution 함수를 작성해주세요.

문제 링크

키포인트

1. 중복되는 경로가 있을 경우, 알파벳이 빠른 순서 부터 체크

• DFS 사용 시, 먼저 읽힌 경로가 우선 탐색되므로 알파벳 순으로 정렬

2. 티켓을 모두 사용해서 다시 돌아 올 수 있도록 해야함.

• 경로와 티켓의 갯수는 1개 차이가 나야 한다.

풀이

1. 먼저 중복 되는 경로가 있을 수도 있으니, 알파벳이 빠른 순서로 정렬

tickets.sortWith(compareBy({ it[0] }, { it[1] }))

2. DFS의 방문 경로를 체크하기 위한 값 추가 및 DFS 재귀

        ticketsUsed = BooleanArray(tickets.size)
        answer = mutableListOf()
        dfs("ICN", mutableListOf("ICN"), tickets)

3. dfs 함수 만들기

• 티켓을 모두 사용 하기 위해서는 경로의 갯수와 티켓의 갯수가 1개 차이가 나야 정답!
• 그게 아닐 경우, DFS 함수를 재귀적으로 호출하며 모두 끝났을 경우, 백트래킹을 통해 다시 탐색 실시

    private fun dfs(current : String,route:MutableList<String>,tickets:Array<Array<String>>){
        // 이미 정답 찾았으면 더 이상 탐색 X
        if (answer.isNotEmpty()) return
        // 현재 루트와 다음 루트가 같다면 리턴
        // 나중에 답보고 안 부분
        // 티켓을 모두 사용하여야 하기때문에 경로와 티켓의 갯수는 1차이가 나야 정답으로 인정해야함.
        if (route.size == tickets.size + 1) {
            answer = route.toList()
            return
        }
        //
        for (i in tickets.indices) {
            if (!ticketsUsed[i] && tickets[i][0] == current) {
                ticketsUsed[i] = true
                route.add(tickets[i][1])
                dfs(tickets[i][1], route, tickets)
                // 백트래킹 사용하여 최소화
                // 여기까지 읽혔다는건 실패했다는 얘기 or 이미 완수 했을 수 있음.
                // 재귀 후 다시 되돌리기
                route.removeAt(route.lastIndex)
                ticketsUsed[i] = false
            }
        }
    }

전체코드

package incava.week4

fun main() {
   val s = Solution()
   val tickets = arrayOf(
       arrayOf("ICN", "JFK"),
       arrayOf("HND", "IAD"),
       arrayOf("JFK", "HND")
   )
   println(s.solution(tickets).toList())
}



class Solution {
   private lateinit var answer: List<String>
   private lateinit var ticketsUsed: BooleanArray


   fun solution(tickets: Array<Array<String>>): Array<String> {
       // 중복되는 경로가 있을 경우, 알파벳이 빠른 순서부터 체크
       // DFS 사용 시, 먼저 읽힌 경로가 우선 탐색되므로 알파벳 순으로 정렬
       tickets.sortWith(compareBy({ it[0] }, { it[1] }))
       ticketsUsed = BooleanArray(tickets.size)
       answer = mutableListOf()
       dfs("ICN", mutableListOf("ICN"), tickets)
       return answer.toTypedArray()
   }



   private fun dfs(current : String,route:MutableList<String>,tickets:Array<Array<String>>){
       // 이미 정답 찾았으면 더 이상 탐색 X
       if (answer.isNotEmpty()) return
       // 현재 루트와 다음 루트가 같다면 리턴
       // 나중에 답보고 안 부분
       // 티켓을 모두 사용하여야 하기때문에 경로와 티켓의 갯수는 1차이가 나야 정답으로 인정해야함.
       if (route.size == tickets.size + 1) {
           answer = route.toList()
           return
       }
       //
       for (i in tickets.indices) {
           if (!ticketsUsed[i] && tickets[i][0] == current) {
               ticketsUsed[i] = true
               route.add(tickets[i][1])
               dfs(tickets[i][1], route, tickets)
               // 백트래킹 사용하여 최소화
               // 여기까지 읽혔다는건 실패했다는 얘기 or 이미 완수 했을 수 있음.
               // 재귀 후 다시 되돌리기
               route.removeAt(route.lastIndex)
               ticketsUsed[i] = false
           }
       }
   }
}