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

해당 문제는 dfs 와 map을 적절히 사용하여 풀 수 있습니다.

저의 경우 처음 코드 작성 시 도시 별 방문 할 수 있는 수를 map에 저장하여 작성하였었으나, 중복 티켓이 있을 경우 티켓의 수와 도시 별 방문 할 수 있는 수 이런 정보가 맞지 않아 테스트케이스 1번을 통과 하지 못하였었습니다.

그러다가 해당 문제의 힌트를 보고 티켓을 기준으로 map에 저장하여 체크를 한다면 정상적으로 모든 티켓을 사용하고 모든 도시를 방문하는 경우를 알 수 있겠구나 싶어 코드를 작성하였습니다.

그리고 해당 문제에 대한 코드를 작성하면서 문제에 따라 조금씩은 상이 하겠지만 data class를 이용하여 데이터의 정규화를 해놓고 비교하는 것이 추후 코드 디버깅을 할 때 문제를 조금 더 빨리 찾고 수정 할 수 있겠구나 라고 생각을 하였습니다.

 

하기는 제가 작성한 코드와 실행 결과 입니다.

class Solution {

    lateinit var visitcount : HashMap<Info,Int> // 해당 지점에 갈 수 있는 횟수
    lateinit var visitList : HashMap<String,ArrayList<String>> // 출발지점에서 갈 수 있는 도시
    var possibly = mutableListOf<Array<String>>()
    var count = 0

    data class Info(
        val start: String,
        val next: String
    )
    
    fun solution(tickets: Array<Array<String>>): Array<String> {
        visitcount = HashMap<Info,Int>() // 해당 지점에 갈 수 있는 횟수
        visitList = HashMap<String,ArrayList<String>>()

        
        for(ticket in tickets){
            if(visitcount.containsKey(Info(ticket[0],ticket[1]))){
                visitcount[Info(ticket[0],ticket[1])] = visitcount[Info(ticket[0],ticket[1])]!!+1
            } else {
                visitcount[Info(ticket[0],ticket[1])] = 1
            }

            if(visitList.containsKey(ticket[0])){
                visitList[ticket[0]]!!.add(ticket[1])
                visitList[ticket[0]]!!.distinct()
            } else {
                var temp = ArrayList<String>()
                temp.add(ticket[1])
                visitList[ticket[0]] = temp
            }
        }

        var temp = Array<String>(2,{""})
        temp[0] = "ICN"
        for(i in 0 .. visitList["ICN"]!!.size-1){
            temp[1] = visitList["ICN"]!![i]
            dfs(Info("ICN",visitList["ICN"]!![i]), temp)
        }

        possibly.sortWith(java.util.Comparator { o1, o2 -> o1.joinToString().compareTo(o2.joinToString()) })
        //println(possibly)

        return possibly.first()
    }

    fun dfs(now: Info,his:Array<String>){

        visitcount[now] = visitcount[now]!!-1

        if(visitcount.values.sum() == 0){
            possibly.add(his)
            visitcount[now] = visitcount[now]!!+1
            return
        }


        var temp = Array<String>(his.size+1,{""})
        if(!visitList[now.next].isNullOrEmpty()){
            for(i in 0 .. his.size-1){
                temp[i] = his[i]
            }
            for(i in 0 .. visitList[now.next]!!.size-1){
                if(visitcount[Info(now.next,visitList[now.next]!![i])]!! > 0){
                    temp[his.size] = visitList[now.next]!![i]
                    dfs(Info(now.next,visitList[now.next]!![i]),temp)
                }
            }
        }
        visitcount[now] = visitcount[now]!!+1
    }

}

실행 결과

테스트 1 〉	통과 (1166.05ms, 392MB)
테스트 2 〉	통과 (9.04ms, 60.5MB)
테스트 3 〉	통과 (11.05ms, 62.2MB)
테스트 4 〉	통과 (14.22ms, 61.4MB)