[프로그래머스] 여행경로

사용 언어: Kotlin

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43164

프로그래머스

출발지점과 도착지점이 담긴 ticket이 있다. ticket을 모두 소모하여 여행경로를 짰을 때, 공항 경로를 return한다.

두 가지 이상의 경로가 있을 때, 사전순으로 빠른 경로를 return한다.

제한사항

tickets = ticket이 담긴 배열

ticket[a,b] = a공항에서 b공항으로 이동하는 티켓

모든 도시를 방문할 수 없는 경우는 주어지지 않는다.

풀이

기본적인 DFS/BFS 문제이다. 출발지와 목적지가 같은 ticket이 있을 수 있다는 것, 동일한 목적지에 2번 이상 도착할 수 있나는 것을 고려해 풀이하면 된다.

ticket 자체를 visit 검사하고, ticket을 순회할 때, 출발지, 목적지가 같은 티켓이 사라지지 않도록 Set, Map을 사용하지 않는다.

코드

fun solution(tickets: Array<Array<String>>): Array<String> {
    val map = mutableMapOf<String, ArrayList<String>>()
    val visitedMap = mutableMapOf<String, ArrayList<Boolean>>()
    tickets.forEach {
        if (map[it[0]] == null) {
            map[it[0]] = arrayListOf()
            visitedMap[it[0]] = arrayListOf()
        }
        map[it[0]]?.add(it[1])
        visitedMap[it[0]]?.add(false)
    }
    map.forEach {
        it.value.sort()
    }
    return dfs(map, visitedMap, "ICN", 0, tickets.size).toTypedArray().reversedArray()
}

fun dfs(map: Map<String, List<String>>, visitedMap: Map<String, ArrayList<Boolean>>, start: String, depth: Int, ticketSize: Int): ArrayList<String> {
    val tickets = map.getOrDefault(start, arrayListOf())
    val visitedList = visitedMap.getOrDefault(start, arrayListOf())

    if(depth == ticketSize) {
        return arrayListOf(start)
    }

    for(i in tickets.indices) {
        if(!visitedList[i]) {
            visitedList[i] = true
            val result = dfs(map, visitedMap, tickets[i], depth + 1, ticketSize)
            if (result.size != 0) {
                result.add(start)
                return result
            }
            visitedList[i] = false
        }
    }
    return arrayListOf()
}