백준 1520 내리막 길

출처: www.acmicpc.net/problem/1520

분류: DP, DFS

---

접근방식

 

DFS 방식으로 원하는 칸에 도달하는 경로를 찾아나갈 수 있습니다. 대신 모든 경우를 탐색하면 시간제한에 걸리게 되므로 DP를 활용해야 합니다.

현재 칸에서 가능한 경우의 수는 이미 모두 탐색을 했기 때문에 방문한 칸을 다시 방문할 필요는 없고 저장된 방문 횟수만 가져옵니다.

구체적으로는 처음에 DP 배열에 -1을 넣어두고 방문하면 0으로 초기화하고 값을 더해줍니다.
DP가 -1일 경우에만 탐색하고 아니면 DP의 값만 리턴합니다.

 

해결방법

typealias Point = (r: Int, c: Int)
let rc = readLine()!.split(separator: " ").map { Int(String($0))! }

var map = [[Int]]()
var dp = [[Int]](repeating: [Int](repeating: -1, count: rc[1]), count: rc[0])
for _ in 0..<rc[0] {
    map.append(readLine()!.split(separator: " ").map { Int(String($0))! })
}

var queue = [Point]()
queue.append((0, 0))

let dr = [-1, 1, 0, 0]
let dc = [0, 0, 1, -1]

func dfs(_ p: Point) -> Int {
    print(p)
    if p.r == rc[0]-1, p.c == rc[1]-1 {
        return 1
    } else if dp[p.r][p.c] == -1 {
        dp[p.r][p.c] = 0
        for d in 0..<4 where 0..<rc[0] ~= p.r + dr[d] && 0..<rc[1] ~= p.c + dc[d] {
            let next = Point(p.r + dr[d], p.c + dc[d])
            if map[next.r][next.c] < map[p.r][p.c] {
                dp[p.r][p.c] += dfs(next)
            }
        }
    }
    
    return dp[p.r][p.c]
}

print(dfs((0, 0)))

 

배운점

이런 경우는 DFS를 써야하는데 BFS에 너무 익숙해져서 생각없이 BFS로 접근했었다.

DP에 기록해두는 아이디어도 메모....

이런 유형을 잘 익혀둬야겠다.