[Swift - 프로그래머스] [카카오 인턴] 경주로 건설

🕵🏻  문제 해석

---

귀여운 죠르디🦖

건설 회사의 회계사인 죠르디는 고객사로부터 경주로 건설 견적 의뢰를 받았습니다. 고객사로 받은 경주로 건설 부지의 정보는 N X N의 격자형태이며 중간중간 벽이 세워져 있는 부분은 1, 비어있는 부지는 0으로 구성되어있었습니다. 

경주로의 시작점은 (0, 0) , 끝 점은 (N - 1, N - 1)이라고 할 때, 벽을 피해 상하좌우로 한 칸씩 도로를 연결 하여 경주로를 완성해야 합니다. 도로는 인접하고 있는 빈 부지 2개를 연결하여 만들고 코너를 만들 때는 500원, 직선도로를 만들 때는 100원이 사용됩니다. 

[제한 사항]

• board는 2차원 정사각 배열로 배열의 크기는 3 이상 25 이하입니다.
• board 배열의 각 원소의 값은 0 또는 1 입니다.
  • 도면의 가장 왼쪽 상단 좌표는 (0, 0)이며, 가장 우측 하단 좌표는 (N-1, N-1)입니다.
  • 원소의 값 0은 칸이 비어 있어 도로 연결이 가능함을 1은 칸이 벽으로 채워져 있어 도로 연결이 불가능함을 나타냅니다.
• board는 항상 출발점에서 도착점까지 경주로를 건설할 수 있는 형태로 주어집니다.
• 출발점과 도착점 칸의 원소의 값은 항상 0으로 주어집니다.

저는 먼저 DFS 알고리즘과 해당 좌표까지 사용되는 최소 금액을 저장할 2차원 배열을 이용하여 문제를 접근했습니다. 그리고 코너를 체크해주기 위해 해당 좌표로 오기 전 방향의 인덱스를 전달 인자로 사용하여 직선일 경우와 방향을 바꿔 코너가 만들어질 때를 나누어 처리해보았습니다. 

📦  문제 풀이 & 코드

---

func solution(_ board:[[Int]]) -> Int {
    let N = board.count
    let dir = [[-1,0,1,0],[0,1,0,-1]]
    
    // 좌표까지 경주로를 건설할 때 사용되는 최소 cost 저장, Int.max값으로 초기화
    var costBoard = [[Int]](repeating: [Int](repeating: Int.max, count: N), count: N)
    
    func isInside(_ r: Int, _ c: Int) -> Bool {
        if r < 0 || r >= N || c < 0 || c >= N {
            return false
        }
        return true
    }
    
    // dir: 현재 위치로 오게된 방향 인덱스
    func dfs(_ cur: (r: Int, c: Int, cost: Int, dir: Int)) {
        
        // 이동한 곳이 벽이거나 배열에 저장된 최솟값 보다 큰 경우 바로 리턴        
        if board[cur.r][cur.c] == 1 || cur.cost > costBoard[cur.r][cur.c] {
            return
        }
        
        // 최솟값으로 갱신
        costBoard[cur.r][cur.c] = cur.cost
    
        // 상하좌우로 탐색
        for idx in 0..<4 {
            let nr = cur.r + dir[0][idx]
            let nc = cur.c + dir[1][idx]
            
            if isInside(nr, nc) {
                // 직전 방향과 같을 경우, cost + 100
                if cur.dir == idx {
                    dfs((r: nr, c: nc, cost: cur.cost + 100, idx))
                } else {
                // 방향을 꺾을 경우 코너 + 직선도로가 생기므로 cost + (100 + 500)
                    dfs((r: nr, c: nc, cost: cur.cost + 600, idx))
                }
            }
        }
    }
    
    // 출발점 cost 0으로 갱신
    
    costBoard[0][0] = 0
    
    // 출발점에선 상하좌우 중 하, 우방향만 가능하므로 두 방향으로 dfs 함수 호출
    
    dfs((r: 0, c: 1, cost: 100, dir: 1))
    dfs((r: 1, c: 0, cost: 100, dir: 2))
    
    // 도착점 최솟값 리턴
    return costBoard[N - 1][N - 1]
}

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

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