여행 경로

⚠️ Warning

ICN -> ATC
ICN -> SFO
SFO -> ATC
이렇게 있다면 ICN->SFO->ATC 만 가능하고 ICN->ATC 는 불가능한 경로가 된다. (SFO로 갈 수 없음)

최단 경로가 아니라, 모든 항공권을 소비하는게 목적이다. 즉, DFS 든 BFS든 ticket size 만큼 depth 가 도달해야한다.

Source code (Kotlin)

오답

class TavelPath {
    fun solution(tickets: Array<Array<String>>): Array<String> {
        val paths = Array<String>(tickets.size + 1){""}

        // 1. 모든 배열에 대해 Map (key: 도시명, value: 목적지 도시명 (SortedSet) 생성
        val map : MutableMap<String, SortedSet<String>> = mutableMapOf()

        for (ticket in tickets) {
            val fromCity  = ticket[0]
            val toCity = ticket[1]
            if (map.get(fromCity) == null) {
                // sorted set is ascending order
                map.put(fromCity, sortedSetOf(toCity))
            } else {
                map.get(fromCity)!!.add(toCity)
            }
        }

        // 시작점은 무조건 ICN
        paths[0] = "ICN"

        // 3. 맵이 비어있을 때 == 간선을 모두 소모 == tickets.size - 1  만큼 반복

        for (i in 1 .. tickets.size) {
            val fromCity = paths[i - 1]
            // 2. Map.get(도시명).first 를 뽑아 정답 리스트에 추가하고
            // 다음 목적지로 go go
            val nextCity = map[fromCity]!!.first()
            paths[i] = nextCity
            map[fromCity]!!.remove(nextCity)
        }

        return paths
    }
}

Tips

DFS 를 통한 백트래킹 및 가지치기를 해야한다.
정답이 발견될 경우 즉시 리턴해야하한다.

간선과 방문 배열

graph 문제처럼 간선을 이어야하지 않을까 싶지만 사실 ticket 그 자체가 출발-목적지를 담고있는 인접행렬이나 다름없다. 방문 배열만 필요하다.

오름차순 먼저 방문

tickets 에 적힌 '목적지'만 오름차순 하면 된다.
그놈이 그놈이기 때문

방문했던 경로 빼주기

이것 때문인데 "즉시" 리턴해서 모든 그전 재귀를 멈출 수가 없나..?

Base condition

1. 더 이상 인접 경로가 없는 경우
   상위 라운드로 다시 되돌아가며 paths 와 visited 처리를 철회해야함. 또, depth 도 하나 이전으로 돌아가야함.

2. 모든 경로를 탐색한 경우
   paths.size == tickets.size + 1
   모든 작업을 즉시 종료시키고 답을 향해가야함.

정답

class TravelPath {
    private fun dfs(tickets: Array<Array<String>>, visited: Array<Boolean>, paths: ArrayList<String>, curCity: String) : Boolean {
        paths.add(curCity)
        // base condition
        if (paths.size == tickets.size + 1) return true

        // 인접 노드 방문
        for (i in tickets.indices) {
            if (!visited[i] && curCity == tickets[i][0]) {
                // 방문처리
                visited[i] = true
                // 최종목적지 도달시 종료,
                // 도달 못했으면 false
                if (dfs(tickets, visited, paths, tickets[i][1])) return true
                // 이거는 약간 국룰룰인데 재귀로 일 끝냈으면 (방문처리 회수해야함)
                // 상위라운드에서 티켓을 다시 사용할 수 있도록.
                visited[i] = false
                paths.removeAt(paths.lastIndex)
            }
        }

        return false
    }
    
    fun solution(tickets: Array<Array<String>>): Array<String> {
        val visited = Array<Boolean>(tickets.size){false}
        tickets.sortBy { it[1] }
        val paths = ArrayList<String>(tickets.size + 1)

        dfs(tickets, visited, paths, "ICN")

        return paths.toTypedArray()
    }
}