프로그래머스 dfs/bfs 여행경로

import java.util.*
class Solution {
      fun solution(tickets: Array<Array<String>>): Array<String> {
        val answer = arrayOf<String>().toMutableList()
        val answerSet = mutableListOf<MutableList<String>>()

        val waitingQue = LinkedList<TicketInfo>() as Queue<TicketInfo>

        val defaultItems = mutableListOf<TicketInfo>()


        //이것도 안에 넣어야함
        tickets.forEachIndexed { index, strings ->
            if (tickets[index][0] == "ICN") {// 사용안하고, 다음티켓의 시작이 지금티켓의 시작과 같다
                defaultItems.add(
                    TicketInfo(
                        tickets[index],
                        1,
                        Array(tickets.size) { false }.apply { set(index, true) },
                        mutableListOf("ICN",tickets[index][1])
                    )
                ) // 다음 티켓 될수 있는것 넣기
            }
        }


        for (i in defaultItems){
            val firstItem = i
            waitingQue.offer(firstItem)
            while (waitingQue.isNotEmpty()) {
                val item = waitingQue.poll()
                if (item.count < tickets.size) {
                    val nextItems = item.next(tickets)

                    if (nextItems.isEmpty()) {

                    } else {
                        for (i in item.next(tickets)) {
                            waitingQue.offer(i)
                        }

                    }
                } else {
                    answerSet.add(item.path)
                }
            }
        }



        println(answer)

        return answerSet[0].toTypedArray()
    }


    class TicketInfo(
        var ticket: Array<String>,
        var count: Int,
        var check: Array<Boolean>,
        var path: MutableList<String>
    )

    fun TicketInfo.next(allTickets: Array<Array<String>>): List<TicketInfo> {
        val tick = mutableListOf<TicketInfo>()
        allTickets.forEachIndexed { index, strings ->
            if (!this.check[index] && this.ticket[1] == allTickets[index][0]) {// 사용안하고, 다음티켓의 시작이 지금티켓의 시작과 같다
                val newPate = this.path.toMutableList()
                newPate.add(allTickets[index][1])
                tick.add(
                    TicketInfo(
                        allTickets[index],
                        this.count + 1,
                        this.check.clone().apply { set(index, true) },
                        newPate // 도착지 저장
                    )
                ) // 다음 티켓 될수 있는것 넣기
            }
        }
        return tick.sortedBy { it.ticket[1] } // 다음 티켓을 반환
    }
}

다른 사람들과 비슷하긴 한데 너무 길다..

class Solution {
    private data class FlightPlan(
        var currentLocation : String,
        val usedTickets : ArrayList<Array<String>> = ArrayList()
    )
    fun solution(tickets: Array<Array<String>>): Array<String> {
        val flightPlanQueue = LinkedList<FlightPlan>(tickets.filter { it[0] == "ICN" }.map {
            FlightPlan(it[1]).also { flightPlan -> flightPlan.usedTickets.add(it)} }
        )
        val possiblePaths = ArrayList<ArrayList<String>>()

        while (flightPlanQueue.isNotEmpty()) {
            val currentFlightPlan = flightPlanQueue.remove()
            if(currentFlightPlan.usedTickets.size == tickets.size) {
                possiblePaths.add(ArrayList<String>().apply {
                    add("ICN")
                    addAll(currentFlightPlan.usedTickets.map{it[1]})
                })
                continue
            }
            tickets.filter {
                it[0] == currentFlightPlan.currentLocation && !currentFlightPlan.usedTickets.contains(it)
            }.forEach {
                flightPlanQueue.offer(FlightPlan(it[1]).also {
                        flightPlan ->
                    flightPlan.usedTickets.addAll(currentFlightPlan.usedTickets)
                    flightPlan.usedTickets.add(it)
                })
            }

        }
        println(possiblePaths.sortedBy { it.toString() }[0].toTypedArray())
        return possiblePaths.sortedBy { it.toString() }[0].toTypedArray()
    }
}

이 분꺼 보니까 그냥 처음에 바로 큐에다가 제일 베이스가될 수 있는 ICN출발 하는 티켓을 넣을 수 있네 이렇게 해야지..

 

 

그리고 tickets에 속한 티켓들이 array로 정의되어 각각 다른 메모리 차지해서 그런지 뭔가 반복되는거 체크해주는 (나는 크기에 맞도록 boolean을 체크해 줬었는데 그럴 필요가 없었다...)