[백준 1890] 점프 (Swift)

https://www.acmicpc.net/problem/1890

 

DP

4
2 3 3 1
1 2 1 3
1 2 3 1
3 1 1 0

 

현재 칸에서 우측 or 아래측으로 이동할 수 있는 칸 수가 각 칸에 명시되어 있는 위의 표를 보고

1,1칸에서 N,N칸에 도달할 수 있는 경우를 출력하는 문제

 

접근방법

DP 배열에 해당 칸까지 오는 경우의 수를 저장한다. 0,0 칸에서 시작하므로 이 칸은 1로 시작해서 맨 위칸 부터 왼쪽에서 오른쪽으로 순회하면서 각 칸에 올 수 있는 경우의 수를 더해가면 된다.

 

처음에는 BFS로 했었는데 그러면 이미 방문한 노드를 다시 방문할 수 있어서 시간복잡도가 더 올라가는 듯

 

오답노트

마지막 칸에 갔을 때는 중복되니까 반복문 돌지 않고 종료해야한다.

 

소스코드

import Foundation

func solution() -> Int {

    // input
    let N:Int = Int(readLine()!)!
    
    var map:[[Int]] = []
    for _ in 0..<N {
        let line = readLine()!.split(separator: " ").map { Int($0)! }
        map.append(line)
    }

    // process
    var dp:[[Int]] = Array<Array<Int>>(repeating: Array<Int>(repeating: 0, count: N), count: N)
    dp[0][0] = 1
    for r in 0..<N {
        for c in 0..<N {
            if map[r][c] == 0 {
                continue
            }
            let nr = r+map[r][c]
            let nc = c+map[r][c]
            if nr < N {
                dp[nr][c] += dp[r][c]
            }
            if nc < N {
                dp[r][nc] += dp[r][c]
            }
        }
    }
    
    return dp[N-1][N-1]
}

print(solution())