[swift] 백준 - 1520번: 내리막 길

1520번: 내리막 길

---

나의 풀이

struct Node { // r,c를 넘겨주기 위한 node
    var r: Int
    var c: Int
}
let MN = readLine()!.split(separator: " ").map { Int($0)! }
let M = MN[0] // 세로의 크기
let N = MN[1] // 가로의 크기
let rx = [0,0,-1,1] // x축 이동
let ry = [1,-1,0,0] // y축 이동
var map = [[Int]]()
var cnt = Array(repeating: Array(repeating: -1, count: N), count: M)
for _ in 0..<M {
    map.append(readLine()!.split(separator: " ").map { Int($0)! })
}

cnt[M-1][N-1] = 1 // DP는 보통 최초 이니셜라이징을 해줘야 함
_ = dfs(now: Node(r: 0, c: 0))
print(cnt[0][0])

func dfs(now: Node) -> Int {
    guard cnt[now.r][now.c] < 0 else { return cnt[now.r][now.c] } // 방문확인
    
    cnt[now.r][now.c] = 0 // 방문처리
    
    for i in 0..<4 {
        let nr = now.r + ry[i] // 열 이동
        let nc = now.c + rx[i] // 행 이동
        if nr < 0 || nc < 0 || nr >= M || nc >= N { // 맵 밖으로 나가는 경우 예외 처리
            continue
        }
        if map[now.r][now.c] > map[nr][nc] {
            cnt[now.r][now.c] += dfs(now: Node(r: nr, c: nc))
            for i in cnt {
                print(i)
            }
            print("")
        }
    }
    return cnt[now.r][now.c]
}

풀이 키워드

DP
DFS

cnt 배열의 흐름

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, 0, 0, 1, 1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, 0, 1, 1, 1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, 1, 1, 1, 1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[1, 1, 1, 1, 1]

[0, -1, -1, -1, -1]
[0, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, 1, 1, 1, 1]

[0, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, 1, 1, 1, 1]

[1, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, -1, -1, -1, -1]
[1, 1, 1, 1, 1]

[1, 0, 0, 0, -1]
[1, -1, -1, 0, -1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, 1]

[1, 0, 0, 0, -1]
[1, -1, -1, 1, -1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, 1]

[1, 0, 0, 1, -1]
[1, -1, -1, 1, -1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, 1]

[1, 0, 0, 1, 0]
[1, -1, -1, 1, 1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, 1]

[1, 0, 0, 1, 1]
[1, -1, -1, 1, 1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, 1]

[1, 0, 0, 2, 1]
[1, -1, -1, 1, 1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, 1]

[1, 0, 2, 2, 1]
[1, -1, -1, 1, 1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, 1]

[1, 2, 2, 2, 1]
[1, -1, -1, 1, 1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, 1]

[3, 2, 2, 2, 1]
[1, -1, -1, 1, 1]
[1, -1, -1, 1, -1]
[1, 1, 1, 1, 1]

---