프로그래머스 배달 문제

계속 해도 한개가 안맞아서.. 다른 사람의 풀이를 보기러 했다.

일단 나의 풀이

import java.util.*
import kotlin.collections.HashSet

class Solution {
    private val hashSet = HashSet<Int>()
    fun solution(N: Int, road: Array<IntArray>, k: Int): Int {
        val q = LinkedList<road>() as Queue<road>
        for (i in road.first( k)) {
            val end = if (i[0] == 1) i[1] else i[0]
            val a = road(1, end, i[2], mutableListOf(i))
            q.offer(a)
        } // 1을 포함하는 모든 로드중에서 시간조건을 만족하는것 추가
        
        while (q.isNotEmpty()) { // 해결 해야되는 조건이 없을 때 까지
            if(hashSet.size == N){
                break
            }
            val pastRoad = q.poll()
            hashSet.add(pastRoad.end) // 갈 수 있는곳 추가

            if (pastRoad.spend < k) { // 시간이 남았는지 확인
                for (i in road.nextRoad(pastRoad.end, pastRoad, k)) {
                    val end = if (i[0] == pastRoad.end) i[1] else i[0]
                    val a = pastRoad.passed
                    a.add(i)
                    val thisRoad = road(pastRoad.end, end, i[2] + pastRoad.spend, a)
                    q.offer(thisRoad)
                }
            }
        }

        hashSet.add(1)
        println(hashSet.size)
        return hashSet.size
    }

    private fun Array<IntArray>.first(k: Int): List<IntArray> {
        return this.filter { (it[0] == 1 || it[1] == 1) && it[2] <= k }
    }
    
    /** 시작점이 그 전 도로의 마지막 지점이며, 지나온 도로를 사용하지 않으면서 가격조건을 만족하는 로드들을 반환*/
    private fun Array<IntArray>.nextRoad(start: Int, th: road, k: Int): List<IntArray> {
        return this.filter { (it[0] == start || it[1] == start) && !th.passed.contains(it) && th.spend + it[2] <= k }
    }

    class road(var start: Int, var end: Int, var spend: Int, var passed: MutableList<IntArray>)
}

 

 

아무리 봐도 뭐가 잘못인지 모르겠다..

 

다른 사람의 풀이

class Solution {
    fun solution(N: Int, road: Array<IntArray>, k: Int): Int {
        var answer:Int = 0
        var len:Int = road.size - 1
    var dist:IntArray = IntArray(N+1, {i->100000000})
    dist[1] = 0
    var flag:Boolean = true

    while(flag){
        flag = false

        for(i in 0..len){
            if(dist[road[i][0]] + road[i][2] < dist[road[i][1]]){
                flag = true
                dist[road[i][1]] = dist[road[i][0]] + road[i][2]
            }
            if(dist[road[i][1]] + road[i][2] < dist[road[i][0]]){
                flag = true
                dist[road[i][0]] = dist[road[i][1]] + road[i][2]
            }
        }
    }

    for(i in 1..N)
    {
        if(dist[i] <= k) answer++
//      println(">>>> ${dist[i]}")
    }

    return answer;
    }
}

 

각 지역까지의 시간을 길을 계쏙 확인하여 더 작은 값으로 초기화 시켜줌 이게 더 낫네.