문제

• 배열이 주워질 때 0.0 왼쪽 위 부터 시작해서 오른쪽 아래까지 벽만 짚고 가고자 한다.

• 한 벽면을 갈 때 1만큼의 시간이 소비된다.

• 이 때 공간에서는 장애물이 존재한다. 장애물의 크기는 1X1이다.

• 장애물이 없는 곳은 0 장애물이 있는 곳은 1 로 [[Int]]형태로 주워진다.

• 이 때 왼쪽 위에서 오른쪽 아래까지 손에 벽을 안 띄고 가고자 한다.

• 이 때 걸리는 최소시간을 구해라. 만약 오른쪽 아래까지 도달하지 못한다면 -1을 반환할 것

코드

func solution(_ road: [[Int]]) -> Int {
    let Y = road.count
    let X = road[0].count

    let temp = [[Bool]](repeating: [Bool](repeating: false, count: X), count: Y)

    var answer = Int.max
    var visited = [temp, temp, temp, temp]

    let dir = ["상", "하", "좌", "우"]

    func dfs(_ y: Int, _ x: Int, _ d: Int, _ count: Int) {
        if visited[d][y][x] { return }
        // 종료
        if y == Y - 1 && x == X - 1 && (d == 3 || d == 1) {
            answer = min(answer, count)
            return
        }

        visited[d][y][x] = true

        if d == 0 {
            if x + 1 < X {
                if road[y][x + 1] == 0 {
                    if y - 1 >= 0, road[y - 1][x + 1] == 0 {
                        dfs(y - 1, x + 1, 2, count + 1)
                    } else {
                        dfs(y, x + 1, d, count + 1)
                    }
                } else {
                    dfs(y, x, 3, count + 1)
                }
            } else {
                dfs(y, x, 3, count + 1)
            }

            if x - 1 >= 0 {
                if road[y][x - 1] == 0 {
                    if y - 1 >= 0, road[y - 1][x - 1] == 0 {
                        dfs(y - 1, x - 1, 3, count + 1)
                    } else {
                        dfs(y, x - 1, d, count + 1)
                    }
                } else {
                    dfs(y, x, 2, count + 1)
                }
            } else {
                dfs(y, x, 2, count + 1)
            }
        }

        if d == 1 {
            if x + 1 < X {
                if road[y][x + 1] == 0 {
                    if y + 1 < Y, road[y + 1][x + 1] == 0 {
                        dfs(y + 1, x + 1, 2, count + 1)
                    } else {
                        dfs(y, x + 1, d, count + 1)
                    }
                } else {
                    dfs(y, x, 3, count + 1)
                }
            } else {
                dfs(y, x, 3, count + 1)
            }
            if x - 1 >= 0 {
                if road[y][x - 1] == 0 {
                    if y + 1 < Y, road[y + 1][x - 1] == 0 {
                        dfs(y + 1, x - 1, 3, count + 1)
                    } else {
                        dfs(y, x - 1, d, count + 1)
                    }
                } else {
                    dfs(y, x, 2, count + 1)
                }
            } else {
                dfs(y, x, 2, count + 1)
            }
        }

        if d == 2 {
            if y + 1 < Y {
                if road[y + 1][x] == 0 {
                    if x - 1 >= 0, road[y + 1][x - 1] == 0 {
                        dfs(y + 1, x - 1, 0, count + 1)
                    } else {
                        dfs(y + 1, x, d, count + 1)
                    }
                } else {
                    dfs(y, x, 1, count + 1)
                }
            } else {
                dfs(y, x, 1, count + 1)
            }
            if y - 1 >= 0 {
                if road[y - 1][x] == 0 {
                    if x - 1 >= 0, road[y - 1][x - 1] == 0 {
                        dfs(y - 1, x - 1, 1, count + 1)
                    } else {
                        dfs(y - 1, x, d, count + 1)
                    }
                } else {
                    dfs(y, x, 0, count + 1)
                }
            } else {
                dfs(y, x, 0, count + 1)
            }
        }

        if d == 3 {
            if y + 1 < Y {
                if road[y + 1][x] == 0 {
                    if x + 1 < X, road[y + 1][x + 1] == 0 {
                        dfs(y + 1, x + 1, 0, count + 1)
                    } else {
                        dfs(y + 1, x, d, count + 1)
                    }
                } else {
                    dfs(y, x, 1, count + 1)
                }
            } else {
                dfs(y, x, 1, count + 1)
            }
            if y - 1 >= 0 {
                if road[y - 1][x] == 0 {
                    if x + 1 < X, road[y - 1][x + 1] == 0 {
                        dfs(y - 1, x + 1, 1, count + 1)
                    } else {
                        dfs(y - 1, x, d, count + 1)
                    }
                } else {
                    dfs(y, x, 0, count + 1)
                }
            } else {
                dfs(y, x, 0, count + 1)
            }
        }
    }
    // 0: 상
    // 1: 하
    // 2: 좌
    // 3: 우
    dfs(0, 0, 0, 1)
    visited = [temp, temp, temp, temp]
    dfs(0, 0, 2, 1)

    return answer == Int.max ? -1 : answer
}

let arr = [
    [0, 0, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 1, 0],
    [0, 0, 0, 0]
]

print(solution(arr))

해결 방법

3차원 배열을 써서 지금 내가 [상 하 좌 우] 중에 어느 벽을 짚고 있는지 알아야하는게 KeyPoint

문제 출저

벽짚고 계단 올라오다가 문제가 떠올라서 문제도 만들고 풀어봤음.

출제 과정 중 생각

Dynamic Programing으로도 풀 수 있지 않을까 싶었는데, 2방향으로 무조권 시작하고 갔던 방향으로 다시 돌아가지 않으니깐 DP는 의미 없는 듯하다.

문제의 KeyPoint는 회전이다. 장애물이 튀어나왔을 때 벽 짚고 회전하는 것을 잘 구현할 수 있느냐가 포인트(?)