Programmers Lv3) [2020 카카오 인턴십] 경주로 건설

출처: programmers.co.kr/learn/courses/30/lessons/67259

분류: Lv3, BFS

---

접근방식

BFS 방식으로 해결했습니다.

조금 확장된 개념이 들어가는데, 단순히 방문 체크에 더해서 비용과 방향까지 기록해주면서 탐색해나가면 됩니다.

방향까지 체크해주는 이유는 같은 가격이여도 어떤 방향에서 오는지에 따라 달라질 수 있기 때문입니다.

현제 체크되어 있는 방향의 비용보다 더 작다면 다시 방문해주는 방식이 되겠습니다.

저는 enum으로 방향을 정의해주고 (그냥 Int나 bool 변수 등으로 정의해도 상관없을 것 같습니다.)

Point 를 하나 정의해서 가지고 있도록 해줬습니다.

enum Direction: Int {
    case horizontal = 0, vertical
}

typealias Point = (r: Int, c: Int, cost: Int, dir: Direction)

 

방향을 체크해서 가격을 책정하는 부분이 조금 귀찮을 수 있는데, 제 방법을 소개해드리면

우선 무조건 도로 건설에는 100원이 들고 방향이 바뀔 때만 500원이 추가되므로, 기본으로 100원을 추가해놓고 방향이 바뀌는지만 판단해서 500원을 더해주는 방식으로 구해줬습니다.

let dr = [-1, 1, 0, 0]
let dc = [0, 0, 1, -1]

for d in 0..<4 where 0..<size ~= r + dr[d] && 0..<size ~= c + dc[d] {
  if d < 2, dir == .horizontal {
    next.cost += 500
    next.dir = .vertical
  } else if d >= 2, dir == .vertical {
    next.cost += 500
    next.dir = .horizontal
  }
}

 

전체 코드를 보시면 이해하는 데 어려운 부분을 없으실 듯 합니다!

 

해결방법

import Foundation

enum Direction: Int {
    case horizontal = 0, vertical
}

func solution(_ board:[[Int]]) -> Int {
    let size = board.count
    typealias Point = (r: Int, c: Int, cost: Int, dir: Direction)
    
    let dr = [-1, 1, 0, 0]
    let dc = [0, 0, 1, -1]

    var price = [[[Int]]](repeating: [[Int]](repeating: [Int](repeating: 2000000, count: 2), count: board.count), count: board.count)
    price[0][0] = [0, 0]
    var queue = [Point]()
    if board[0][1] == 0 {
        price[0][1][0] = 100
        queue.append(Point(0,1,100,.horizontal))
    }
    if board[1][0] == 0 {
        price[1][0][1] = 100
        queue.append(Point(1,0,100,.vertical))
    }

    while !queue.isEmpty {
        let (r, c, cost, dir) = queue.removeFirst()
        
        for d in 0..<4 where 0..<size ~= r + dr[d] && 0..<size ~= c + dc[d] {
            let dr = r + dr[d]
            let dc = c + dc[d]
            
            guard board[dr][dc] == 0 else { continue }
            
            var next = Point(dr, dc, cost+100, dir)
            
            if d < 2, dir == .horizontal {
                next.cost += 500
                next.dir = .vertical
            } else if d >= 2, dir == .vertical {
                next.cost += 500
                next.dir = .horizontal
            }
            
            if price[dr][dc][next.dir.rawValue] > next.cost {
                price[dr][dc][next.dir.rawValue] = next.cost
                queue.append(next)
            }
        }
    }
    
    return price[size-1][size-1].min()!
}

 

배운점

 ㄱ ㄱ ㄱ ㄱ ㄱ ㄱ ㄱ ㄲ 나도 합격로 건설하고 싶다 🔥