[Programmers] 카카오 인턴십 - 경주로 건설 (Swift)

문제 : 

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

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

 

문제 설명에 앞서, 테스트 케이스 14, 24에서 막혀서 질문하기에 다른 분들이 올려놓은 예외 테스트 케이스를 한정적으로 풀어가며 해결했기 때문에 솔루션같은 풀이는 아니라는 점 말씀드립니다.

 

Step 1. 문제 이해하기

• 출발점 (0, 0)에서 도착점 (N - 1, N - 1)에 도착하기 위해서 비용이 최소가 되도록 도로를 건설하려고 합니다.
• 직선도로를 설치할 수 있는데, 직선도로 2개가 서로 직각으로 만나는 지점을 코너라고 합니다.
• 이때, 직선도로 하나를 만들 때 100원, 코너를 하나 만들 때 500원의 지출이 발생합니다.
• board는 2차원 정사각 배열, 크기는 3 이상 25 이하

 

Step 2. 문제 풀이 생각하기

1. 처음에 '완전 탐색을 해야겠구나' 싶어서 bfs로 생각을 했습니다. 거기서 가중치가 나와서 다익스트라 형태로 전환했습니다.
2. 먼저 해당 지점까지의 비용을 알기 위해서 dp로 사용할 nBoard을 새로 만들었습니다. (0, 0)은 0, 벽은 -1, 나머지는 Int.max
3. 방향은 0 : 북, 1 : 남, 2 : 서, 3 : 동, 4 : 방향 없음 -> (0, 0)
4. 다음 좌표를 탐색할 때 이전 좌표의 방향과 다를 때(북, 남 <-> 서, 동)와 같을 때([서, 동 == 서, 동], [북, 남 == 북, 남]) 를 나누어서 다르면 600, 같으면 100을 비용에서 추가하는 방식으로 구현
5. 큐에 [비용, 행 좌표, 열 좌표, 방향]을 저장하고 큐에서 remove 할 때는 비용 기준 정렬 후 제거했습니다.
6. 그렇게 구현했을 때 테스트 케이스 14, 24가 틀려서 질문 목록에 있는 테스트 케이스를 "임시방편"이라고 주석처리 else문 2개로 해결할 수 있었습니다.

 

문제 첫 번째 예시에서 직선도로는 100의 비용이 들고, 코너를 포함한 직선은 그 직선의 끝 지점에 해당하는 다음 지점에 비용을 책정합니다. 결국 100 + 500 = 600으로 처리를 할 수 있습니다.

이해가 안 되는 예외 테스트 케이스가 있다면 그리면서 풀이해보는 것을 추천합니다.

 

Step 3. 차근차근 구현하기

// 뱡향 : 0 : 북, 1 : 남, 2 : 서, 3 : 동, 4: 방향 없음 -> (0,0)
import Foundation
func solution(_ board:[[Int]]) -> Int {
    var nBoard = [[Int]](repeating: Array(repeating: Int.max, count: board.count), count: board.count)
    nBoard[0][0] = 0
    for i in 0..<board.count {
        for j in 0..<board.count {
            if board[i][j] == 1 {
                nBoard[i][j] = -1
            }
        }
    }
    let d : [[Int]] = [[-1, 0], [1, 0], [0, -1], [0, 1]]
    var ans = 0
    
    // 맵을 넘어 갔을 때 처리
    func boundary(i : Int, j : Int) -> Bool {
        return (0 <= i && i < board.count) && (0 <= j && j < board.count)
    }
    
    func bfs() {
        var q : [[Int]] = [[0, 0, 0, 4]]
        while !q.isEmpty {
            q.sort(by: {$0[0] < $1[0]}) // 비용 기준 정렬
            let (c, i, j, nd) = (q[0][0], q[0][1], q[0][2], q[0][3])
            q.removeFirst()
            
            // 도착지점에 가장 먼저 도착한 비용을 출력
            if i == board.count - 1 && j == board.count - 1 {
                ans = nBoard[board.count - 1][board.count - 1]
                return
            }
            
            // 이전 지점과 동일한 방향일 때는 비용 + 100, 다르면 비용 + 600
            for k in 0..<d.count {
                let ni = i + d[k][0]
                let nj = j + d[k][1]
                // 범위를 넘어가거나 벽이 나왔을 때 넘어가기
                if !boundary(i : ni, j : nj) || nBoard[ni][nj] == -1 {
                    continue
                }
                if (k == 0) && (nd != 2 && nd != 3) {
                    if nBoard[ni][nj] >= c + 100 {
                        nBoard[ni][nj] = c + 100
                        q.append([nBoard[ni][nj], ni, nj, k])
                    }
                }
                else if (k == 0) && (nd == 2 || nd == 3) {
                    if nBoard[ni][nj] >= c + 600 {
                        nBoard[ni][nj] = c + 600
                        q.append([nBoard[ni][nj], ni, nj, k])
                    }
                }
                else if (k == 1) && (nd != 2 && nd != 3) {
                    if nBoard[ni][nj] >= c + 100 {
                        nBoard[ni][nj] = c + 100
                        q.append([nBoard[ni][nj], ni, nj, k])
                    }
                    else {
                        q.append([c + 100, ni, nj, k]) // 임시방편
                    }
                }
                else if (k == 1) && (nd == 2 || nd == 3) {
                    if nBoard[ni][nj] >= c + 600 {
                        nBoard[ni][nj] = c + 600
                        q.append([nBoard[ni][nj], ni, nj, k])
                    }
                }
                else if (k == 2) && (nd != 0 && nd != 1) {
                    if nBoard[ni][nj] >= c + 100 {
                        nBoard[ni][nj] = c + 100
                        q.append([nBoard[ni][nj], ni, nj, k])
                    }
                }
                else if (k == 2) && (nd == 0 || nd == 1) {
                    if nBoard[ni][nj] >= c + 600 {
                        nBoard[ni][nj] = c + 600
                        q.append([nBoard[ni][nj], ni, nj, k])
                    }
                }
                else if (k == 3) && (nd != 0 && nd != 1) {
                    if nBoard[ni][nj] >= c + 100 {
                        nBoard[ni][nj] = c + 100
                        q.append([nBoard[ni][nj], ni, nj, k])
                    }
                    else {
                        q.append([c + 100, ni, nj, k]) // 임시방편
                    }
                }
                else if (k == 3) && (nd == 0 || nd == 1) {
                    if nBoard[ni][nj] >= c + 600 {
                        nBoard[ni][nj] = c + 600
                        q.append([nBoard[ni][nj], ni, nj, k])
                    }
                }
            }
        }
    }
    bfs()
    return ans
}

print(solution([[0,0,0],[0,0,0],[0,0,0]])) // 답 : 900
print(solution([[0,0,0,0,0,0,0,1],[0,0,0,0,0,0,0,0],[0,0,0,0,0,1,0,0],[0,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1],[0,0,1,0,0,0,1,0],[0,1,0,0,0,1,0,0],[1,0,0,0,0,0,0,0]])) // 답 3800
print(solution([[0,0,1,0],[0,0,0,0],[0,1,0,1],[1,0,0,0]])) // 답 : 2100
print(solution([[0,0,0,0,0,0],[0,1,1,1,1,0],[0,0,1,0,0,0],[1,0,0,1,0,1],[0,1,0,0,0,1],[0,0,0,0,0,0]])) // 답 : 3200
print(solution([[0, 0, 0, 0, 0], [0, 1, 1, 1, 0], [0, 0, 1, 0, 0], [1, 0, 0, 0, 1], [0, 1, 1, 0, 0]])) // 답 : 3000
print(solution([[0, 1, 1, 1, 1, 1, 1, 1, 1],
                [0, 0, 0, 0, 0, 1, 1, 1, 1],
                [1, 1, 1, 1, 0, 1, 1, 1, 1],
                [0, 0, 0, 0, 0, 1, 1, 1, 1],
                [0, 1, 0, 1, 1, 1, 1, 1, 1],
                [0, 1, 0, 0, 0, 1, 1, 1, 1],
                [0, 1, 1, 1, 0, 1, 1, 1, 1],
                [0, 0, 0, 0, 0, 1, 1, 1, 1],
                [1, 1, 1, 1, 0, 0, 0, 0, 0]])) // 답 : 5500

 

Step 4. 피드백

• 5시간 정도 걸린 것 같은데 어려운 문제였지만, 어쨌든 해결했다는 것이 뿌듯하고 문제 풀이 시간을 더 줄일 수 있도록 더 많은 문제를 풀어봐야될 것 같습니다.