[Swift 알고리즘] 프로그래머스(Lv.3) - 경주로 건설 / 2020 카카오 인턴십

안녕하세요. 개발 중인 정주입니다.

 

오늘은 "프로그래머스(Lv.3) - 경주로 건설" 문제를 풀었습니다.

 

---

 

Github

GitHub - jeongju9216/SwiftAlgorithm: 스위프트 알고리즘

 

문제 링크

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

 

---

풀이

이번 문제는 dfs + dp 문제입니다.

문제를 푼 후 검색을 해보니 bfs, 3차원 배열 등 여러 가지 방법이 있었습니다.

제 풀이가 어려우시다면 다른 분의 풀이도 참고해 보세요.

 

1. Car라는 구조체를 선언해주었습니다.

struct Car {
    var x: Int //세로 이동
    var y: Int //가로 이동
    var cost: Int //지금까지의 비용
    var prev: Int //이전 이동 방향
}

x, y 좌표와 지금까지의 비용을 담는 cost, 이전의 이동 방향을 저장하는 prev 속성이 존재합니다.

참고로 x가 세로축 이동, y가 가로축 이동입니다.

 

2. 지금까지의 최소 cost를 저장하는 2차원 배열 visited를 정의합니다.

var visited: [[Int]] = Array(repeating: Array(repeating: Int.max - 500, count: length), count: length)

위에서 언급했듯이 visited는 방문을 했는가, 하지 않았는가를 체크하는 것이 아니라 최소 cost를 저장하는 용도입니다.

따라서 Bool이 아니라 Int 배열로 만들었습니다.

 

Int.max에서 500을 빼준 이유는 아래에서 설명합니다. 이 500이 핵심 포인트입니다!!

 

3. dfs를 이용해 (0,0)에서 (n-1, n-1)로 이동하는 cost를 계산합니다.

상하좌우를 1칸씩 움직이면서 재귀를 실행합니다.

이때, cost와 방향성을 저장하면서 이동을 합니다.

cost는 직진이라면 100을, 좌회전 혹은 우회전을 한다면 600원을 더해야 합니다.

 

visited에 저장된 cost가 위에서 더한 cost보다 클 때 이동합니다.

지금 가는 경로가 최소 비용 경로이니 갱신을 하겠다는 의미입니다.

만약 현재 cost가 더 크다면 해당 경로 탐색을 중단합니다.

 

하지만 한 가지 생각해야 하는 상황이 있습니다. (질문 게시판 hwan님의 질문)

바로 중간 과정 중에는 cost가 더 크지만 최종 결과는 더 작은 경우입니다.

테스트 케이스 25번에서 계속 실패한다면 이 상황을 고려하지 않은 것입니다.

 

위 그림에서 최소 비용은 3000이지만 아래 방향을 먼저 탐색할 경우 3300의 결과가 나오는데요.

두 경로가 겹쳐지는 지점에서 아래 방향 경로는 2100, 오른쪽 방향 경로는 2300 입니다.

따라서 오른쪽 방향을 나중에 가게 되면 접점에서 탐색을 중단하게 되기 때문입니다.

 

이 케이스는 visited[x][y] + 500 > cost 조건을 체크하면 해결이 가능합니다.

코너 1개만큼은 차이가 나도 탐색을 계속 진행하는 것입니다.

코너가 2개 이상 차이나는데 결과가 최소 비용인 경우는 존재할 수 없습니다.

 

4. 마지막에 visited[n-1][n-1]을 출력하면 답이 됩니다.

 

저는 3번에서 예외 테스트 케이스를 찾지 못해 도움을 받았습니다.

이런 테스트 케이스를 찾는 것도 실력인데 전 아직 많이 부족한가 봅니다 ㅠㅠ

열심히 해야겠습니다

 

감사합니다!

 

---

전체 코드

import Foundation

struct Car {
    var x: Int
    var y: Int
    var cost: Int
    var prev: Int
}

let dx: [Int] = [-1, 1, 0, 0] //상하좌우
let dy: [Int] = [0, 0, -1, 1]

func solution(_ board:[[Int]]) -> Int {
    let length = board.count
    var visited: [[Int]] = Array(repeating: Array(repeating: Int.max - 500, count: length), count: length)
    
    func moveCar(_ car: Car) {
        for i in 0..<4 {
            let nx = car.x + dx[i]
            let ny = car.y + dy[i]
            var nCost = car.cost + 100
            if car.prev >= 0 && car.prev != i {
                nCost += 500
            }

            if (0..<length) ~= nx && (0..<length) ~= ny {
                if visited[nx][ny] + 500 > nCost && board[nx][ny] == 0 {
                    if visited[nx][ny] > nCost {
                        visited[nx][ny] = nCost    
                    }
                    
                    moveCar(Car(x: nx, y: ny, cost: nCost, prev: i))
                }
            }
        }
    }
    
    moveCar(Car(x: 0, y: 0, cost: 0, prev: -1))
    
    return visited.last!.last!
}

---

아직은 초보 개발자입니다.

더 효율적인 코드 훈수 환영합니다!

공감과 댓글 부탁드립니다.