[알고리즘 연습] 경주로 건설 (프로그래머스 lv3, 스위프트)

문제

https://programmers.co.kr/learn/courses/30/lessons/67259

코딩테스트 연습 - 경주로 건설

풀이

func solution(_ board:[[Int]]) -> Int {
    let n = board.count
    let dx = [1,-1,0,0]
    let dy = [0,0,1,-1]
    var distance = Array(repeating: Array(repeating: [Int.max, Int.max], count: n), count: n)
    distance[0][0] = [0,0]

    var stack = [(x:0,y:0,d:0)]

    while stack.count > 0 {
        let now = stack.removeLast()

        let x = now.x
        let y = now.y
        let d = now.d

        for i in 0...3 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            let nd = i < 2 ? 0 : 1
            var value = d == nd ? distance[y][x][d] + 100 : distance[y][x][d] + 600
            if y == 0 && x == 0 { value = 100 }
            if nx >= 0 && nx < n && ny >= 0 && ny < n && 
            distance[ny][nx][nd] > value && 
            board[ny][nx] == 0 {
                distance[ny][nx][nd] = value
                stack.append((x:nx, y:ny, d: nd))
            }
        }
    }

    return min(distance[n-1][n-1][0],distance[n-1][n-1][1])
}

• stack에 방향성정보(d)를 포함시키는 것이 핵심인 문제였다.
• 마찬가지로 현재까지의 비용을 기록하는 distance도 3차원으로 이루어져야 한다. (가로방향과 세로방향을 각각계산해야하기 때문)
• 이런식으로 다익스트라 문제에 간단한 응용을 더하는 경우가 많은 것 같다. 잘 분석해보면 응용은 별거없고 똑같은 다익스트라 문제이니 너무 어렵게 생각하지 말자.

func solution(_ board:[[Int]]) -> Int {
    let n = board.count
    let dx = [1,-1,0,0]
    let dy = [0,0,1,-1]
    var distance = Array(repeating: Array(repeating: [Int.max, Int.max], count: n), count: n)
    distance[0][0] = [0,0]

    var queue = [(x:0,y:0,d:0)]
    var head = 0
    while queue.count - head > 0 {
        let now = queue[head]
        head += 1

        let x = now.x
        let y = now.y
        let d = now.d

        for i in 0...3 {
            let nx = x + dx[i]
            let ny = y + dy[i]
            let nd = i < 2 ? 0 : 1
            var value = d == nd ? distance[y][x][d] + 100 : distance[y][x][d] + 600
            if y == 0 && x == 0 { value = 100 }
            if nx >= 0 && nx < n && ny >= 0 && ny < n && 
            distance[ny][nx][nd] > value && 
            board[ny][nx] == 0 {
                distance[ny][nx][nd] = value
                queue.append((x:nx, y:ny, d: nd))
            }
        }
    }

    return min(distance[n-1][n-1][0],distance[n-1][n-1][1])
}

• tip) stack으로도 통과가 되지만 head값을 통해 간단한 queue를 만들어 사용하면 더 효율적인 해결이 가능하다.