[프로그래머스] lv3. 경주로 건설(with Swift)

DFS 대신 재귀로 구현하려다가 코드가 무지 복잡해졌다. ㅠㅠ 때려치고 다른 사람의 풀이를 봤다. ㅠㅠ 결국 DFS나 BFS로 풀면 되는 문제였다. 난 진자 왜 이렇게 바보인 걸까... 앞날이 걱정된다.
해결법 알려드립니다 : 그냥 열심히 하셈.
그래 이런 문제 한 100개 풀면 101번째는 풀 수 있겠지. 근데 100개 푸는 사이에 시간이 많이 흐를거다. 조급한 마음.ㅋㅋ 지금 당장 잘해지고 싶지만 뭐 어쩔겨...
접근법 한번 틀리면 진짜 시간이 많이 소모된다. 좀 더 깔끔한 구상에 시간을 쏟는 것이 필요하다.

문제

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

프로그래머스

길어서 설명은 따로 옮기지 않겠습니다.

[아이디어]
1. 완탐이다 -> BFS
2. 큐의 첫번째 노드를 방문하면서, 가능한 이웃 노드들의 cost를 모두 업데이트한다.
3. cost가 업데이트되면 업데이트 된 이웃 노드의 위치와 업데이트하는데 필요한 이동방향, cost를 큐에 넣고, 반복한다.
4. 출발할 때 아래쪽으로 가는 경우와 오른쪽으로 가는 경우가 있으므로, 각 경우에 대해 모두 탐색 해야 한다.

[메인 로직(BFS) 구상]
(현재까지 탐색 결과 minimum cost를 저장하는 2차원 배열을 사전에 설정해 둔다. INF에 준하는 값으로 초기화한다.)
1. 큐의 첫번째 원소를 now에 두고 삭제.
2. now의 좌표, cost, 직전 이동방향 저장
3. 모든 이동방향(아래, 위, 오른, 왼)에 대해
3-1. now를 한칸 이동해 본다.
3-2. 이동 결과가 부적절한 경우, 이 방향으로 갈 수 없으므로 continue (부적절: 맵 밖에 있거나, 장애물 위치인 경우)
3-3. 이동 결과가 적절한 경우, 이 방향으로 도착한 이웃 노드의 원래 cost와 now를 거쳐 도착했을 때의 cost를 비교한다.
1) 원래 cost가 now를 거쳐 도착했을 때의 cost보다 크거나 같은 경우, 이웃 노드의 cost를 now를 거쳐 도착했을 때의 cost로 저장하고, 이 cost와 이웃노드 좌표, 이동방향(now에서 이웃노드까지의)을 큐에 넣는다.
4. 1-3의 과정을 큐가 비지 않을 때까지 반복한다.
5. 도착 지점의 cost를 반환한다.

[주의사항]
1. 현재 노드의 모든 이웃 노드를 탐색해야 한다.
2. "원래 cost가 now를 거쳐 도착했을 때의 cost보다 크거나 같은 경우" 에서 같은 경우를 포함시키는 것이 중요하다. cost가 같다고 하더라도, 원래 cost가 now를 거쳐 도착했을 때와 다른 방향으로 계산된 것일 수 있다. 즉 이동 방향이 다른 상태에서 해당 노드에 도착한 것일 수 있다. 그리고 이동 방향은 앞으로의 cost에도 영향을 미칠 수 있다. ((n,n-1)에 두 경로 다 C cost로 도착했는데 하나는 위에서, 하나는 왼쪽에서 온 경로라면 왼쪽에서 온 경로가 직진을 택할 수 있기 때문에 더 적은 cost를 가지게 된다.)

[코드]

import Foundation
// 0 : down
// 1 : up
// 2 : right
// 3 : left
let INF: Int = Int(2e9)

func move(_ x: Int, _ y: Int, _ n: Int, _ move: Int) -> (Int, Int) {
    if move == 0 {
        if y == n-1 { //invalid(out of map) movement
            return (-1, -1)
        }
        return (x, y+1)
    }
    else if move == 1 {
        if y == 0 { //invalid(out of map) movement
            return (-1, -1)
        }
        return (x, y-1)
    }
    else if move == 2 {
        if x == n-1 { //invalid(out of map) movement
            return (-1,-1)
        }
        return (x+1, y)
    }
    else if move == 3 {
        if x == 0 { //invalid(out of map) movement
            return (-1, -1)
        }
        return (x-1, y)
    }
    return (-1, -1)
}

func BFS(_ board:[[Int]],_ x:Int, _ y:Int, _ startmove:Int) -> Int {
    var candidate :[Int] = []
    var queue :[(Int, Int, Int, Int)] = [(x, y, 0, startmove)]
    var cost : [[Int]] = Array(repeating: Array(repeating: INF, count: board.count), count: board.count)
    
    while !queue.isEmpty {
        var (now_x, now_y, now_cost, prevmove) = queue.removeFirst()
        
        for i in 0...3 {
            var movedPoint = move(now_x, now_y, board.count, i)
            if movedPoint == (-1, -1) || board[movedPoint.0][movedPoint.1] == 1 {
                //invalid movement : (out of map) + (on the obstacle)
                continue
            }
            else {
                var dist = 0
                if i == prevmove {
                    dist = 100 //go straight
                }
                else {
                    dist = 600 //curve
                }
                if cost[movedPoint.0][movedPoint.1] >= now_cost + dist {
                    cost[movedPoint.0][movedPoint.1] = now_cost + dist
                    queue.append((movedPoint.0, movedPoint.1, now_cost + dist, i))
                }
                
            }
        }
    }
    return cost[board.count-1][board.count-1]
}

func solution(_ board:[[Int]]) -> Int {
	// calculate both left-start & down-start cases
    return min(BFS(board, 0, 0, 0), BFS(board, 0, 0, 2)) 
}

틀렸거나 더 나은 풀이가 있으면 말씀해 주세요
오늘도 행복한 하루