[프로그래머스] Summer/Winter Coding(~2018) 배달 with Swift

안녕하세요. 오늘은 프로그래머스 배달 문제를 풀어보겠습니다.

배달문제는 단순 BFS로 풀게되면 32번에서 timeout이나는 문제이기 때문에

 

BFS를 다익스트라 알고리즘을 적용하여 문제를 풀어야합니다.

 

다익스트라 알고리즘은 이름처럼 막 익스트림하게 어려운 알고리즘이 아닙니다.

 

그냥 노드에 최단거리일 경우 업데이트 해주고 Queue에 넣어주면 됩니다.

 

이제 문제를 풀어보겠습니다.

 

 

1. 이차원 배열을 이용하여 그래프를 만들어줍니다.

var graph:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: N+1), count: N+1)
for i in road {
    if graph[i[0]][i[1]] != 0 {
        graph[i[0]][i[1]] = i[2] > graph[i[0]][i[1]] ? graph[i[0]][i[1]] : i[2]
        graph[i[1]][i[0]] = i[2] > graph[i[1]][i[0]] ? graph[i[1]][i[0]] : i[2]
    }
    else {
        graph[i[0]][i[1]] = i[2]
        graph[i[1]][i[0]] = i[2]
    }
}

 

2. BFS를 시작하기 이전 Queue를 init하여 줍니다.

for i in 1...N {
    if graph[1][i] != 0 {
        var newNode:Infomation = Infomation()
        newNode.currentPosition = i
        newNode.timeTaken = graph[1][i]
        bfsQueue.append(newNode)
        answerMap[i] = newNode.timeTaken
    }
}

 

3. 다익스트라 알고리즘을 수행하여 줍니다.

while bfsQueue.isEmpty != true {
    for i in 2...N {
        if graph[bfsQueue[0].currentPosition][i] != 0 {
            var newNode = bfsQueue[0]
            newNode.currentPosition = i
            newNode.timeTaken += graph[bfsQueue[0].currentPosition][i]
            if answerMap[i] == 0 || newNode.timeTaken < answerMap[i]{
                bfsQueue.append(newNode)
                answerMap[i] = newNode.timeTaken
            }
        }
    }
    bfsQueue.removeFirst()
}

 

이후 거리가 k미만인 노드의 갯수를 구해주시면 문제를 해결할 수 있습니다.

 

import Foundation

struct Infomation {
    var currentPosition:Int = 0
    var timeTaken:Int = 0
}

func solution(_ N:Int, _ road:[[Int]], _ k:Int) -> Int {
    var answer = 0
    var answerMap:[Int] = [Int](repeating: 0, count: N+1)
    answerMap[1] = 0
    var graph:[[Int]] = [[Int]](repeating: [Int](repeating: 0, count: N+1), count: N+1)
    var bfsQueue:[Infomation] = [Infomation]()
    
    // Make Graph
    for i in road {
        if graph[i[0]][i[1]] != 0 {
            graph[i[0]][i[1]] = i[2] > graph[i[0]][i[1]] ? graph[i[0]][i[1]] : i[2]
            graph[i[1]][i[0]] = i[2] > graph[i[1]][i[0]] ? graph[i[1]][i[0]] : i[2]
        }
        else {
            graph[i[0]][i[1]] = i[2]
            graph[i[1]][i[0]] = i[2]
        }
    }

    // BFS Queue Init
    for i in 1...N {
        if graph[1][i] != 0 {
            var newNode:Infomation = Infomation()
            newNode.currentPosition = i
            newNode.timeTaken = graph[1][i]
            bfsQueue.append(newNode)
            answerMap[i] = newNode.timeTaken
        }
    }
    
    //BFS
    while bfsQueue.isEmpty != true {
        for i in 2...N {
            if graph[bfsQueue[0].currentPosition][i] != 0 {
                var newNode = bfsQueue[0]
                newNode.currentPosition = i
                newNode.timeTaken += graph[bfsQueue[0].currentPosition][i]
                if answerMap[i] == 0 || newNode.timeTaken < answerMap[i]{
                    bfsQueue.append(newNode)
                    answerMap[i] = newNode.timeTaken
                }
            }
        }
        bfsQueue.removeFirst()
    }
    
    // Make Answer
    print(answerMap)
    for i in 1..<answerMap.count {
        if answerMap[i] <= k {
            answer += 1
        }
    }
    
    return answer
}

 

오늘은 여기까지 입니다! 질문이 있으시면 댓글로 남겨주세요!

 

감사합니다.