2024.01.19(금) TIL

오늘은 프로그래머스 여행경로 문제를 풀었다.

프로그래머스 여행경로

DFS로 푸는 문제인데, 까다로운 부분은 가능한 경로가 2개 이상일 경우에는 알파벳 순서가 앞서는 순서를 return 해줘야했다.
나는 스택과 DFS를 이용해서 풀어줬다.

import java.util.Stack
class Solution {
    private var visit = booleanArrayOf()
    val answer = mutableListOf<String>()
    val stack = Stack<String>()
    fun solution(tickets: Array<Array<String>>): Array<String> {
        for(i in tickets.indices){
            if(tickets[i][0]=="ICN"){
                visit = BooleanArray(tickets.size){false}
                visit[i] = true
                stack.push("ICN")
                stack.push(tickets[i][1])
                dfs(tickets,1)
                stack.pop()
                stack.pop()
            }
        }
        return answer.sorted()[0].split(",").toTypedArray()
    }

    private fun dfs(tickets: Array<Array<String>>, dept: Int) {
        if(dept == tickets.size) answer.add(stack.joinToString(","))
        val nextDestination = stack.peek()
        for(i in tickets.indices){
            if(visit[i]) continue
            if(tickets[i][0] == nextDestination){
                visit[i] = true
                stack.push(tickets[i][1])
                dfs(tickets, dept+1)
                stack.pop()
                visit[i] = false
            }
        }
    }

}