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

문제 : programmers.co.kr/learn/courses/30/lessons/43164

코딩테스트 연습 - 여행경로

 

 

lateinit var visit : MutableList<Boolean> // 티켓 사용 여부
val answer = mutableListOf<String>() // 정답
val temp = mutableListOf<String>() // 임시 저장용
lateinit var tickets_ : Array<Array<String>> // 티켓 전역변수

fun solution(tickets: Array<Array<String>>): Array<String> {
    visit = MutableList(tickets.size) { false }
    tickets.sortBy { it[1] } // 알파벳 순서가 앞서는 경로 return 하기 위함
    tickets_ = tickets
    dfs("ICN",0)
    return answer.toTypedArray()
}

fun dfs(str : String , x : Int) : Boolean {
    temp.add(str)

    // 탐색이 무사히 성공했을 때
    if (x == tickets_.size){
        answer.addAll(temp)
        return true
    }

    for(i in tickets_.indices){
        // 현재 위치와 같고, 사용하지 않은 티켓일 때
        if (tickets_[i][0] == str && ! visit[i]){
            visit[i] = true
            if (dfs(tickets_[i][1], x + 1)) return true
            // 탐색 실패 시 방문 처리 취소
            visit[i] = false
        }
    }
    temp.removeAt(temp.size-1)
    return false
}

일반적인 dfs가 아니라 티켓을 다 써야하므로

A->B , A->C, C->A 같은 티켓이 주어질 때를 따로 처리해줘야 해서 애를 먹었던 문제이다.

단순히 알파벳 순으로 정렬한다면 A->B 로 간후 더이상 갈수 있는 곳이 없다.

여기서 B를 빼버리고 C를 탐색해야한다.

저 경우에 스택처럼 맨 위의 원소를 삭제했다.