[DFS + DP] 백준 1520번: 내리막길(Swift)

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

1520번: 내리막 길

 

 

난이도: 골드 3

사용언어: Swift

카테코리: DFS + DP

풀이과정

문제를 보자마자 단순 DFS 문제라고 생각해서 DFS만 이용하여 탐색하였다.

하지만, 첫 제출에서 시간 초과가 발생...

시간 초과의 원인은, 문제 특성상 map에서 다른 경로이지만, 중복되는 경로가 존재할 수 있다. 가령

위 그림 처럼 50부터 32까지 두 경로가 겹친다. 이런점을 이용하여 DP(Dynamic Programming)를 이용하여 시간 초과를 해결할 수 있었다.

 

DP는 해당 지점의 경우의 수를 저장해 두어야한다. 먼저,

탐색이 종착지에 도착하면, dfs 메서드는 1을 리턴하도록 하여 한가지 경우의 수를 찾았다는 의미이다.

반복문, 내부에서는 다음 이동할 좌표에 DP가 0보다 크면, 이미 탐색을 했고, 해당 지점부터 종착지 까지 경우의 수를 구한 상태 이를 해당(start) 좌표에 + 해준다.

이동할 좌표에 DP가 0이면, 아직 탐색이 되지 않은 상태이기 때문에 dfs를 재귀로 호출하여 종착지 또는 DP가 0보다 큰 지점이 나올때 까지 탐색한다.

 

반복문이 끝나고, 해당 좌표의 DP가 0이면 종착지까지 가지 못했다는 의미이기 때문에 해당 경로를 탐색하지 않기 위해 -1을 리턴하여 해당 경로는 탐색하지 않게 하고, 0이 아니면, 해당 좌표의 DP를 반환하여 부모 좌표의 DP에 + 될 수 있도록 한다.

 

code

let mn = readLine()!.split(separator: " ").map { Int($0)! }
let m = mn[0]
let n = mn[1]

var map = [[Int]]()
var dp = Array(repeating: Array(repeating: 0, count: n), count: m)

for _ in 0..<m {
  let y = readLine()!.split(separator: " ").map { Int($0)! }
  map.append(y)
}

let direction: [(y: Int, x: Int)] = [
  (0,-1),
  (0,1),
  (-1,0),
  (1,0)
]



func dfs(start: (y: Int, x: Int)) -> Int {
  if start == (m - 1, n - 1) {
    return 1
  }
  
  for i in 0..<direction.count {
    let nP: (y: Int, x: Int) = (start.y + direction[i].y, start.x + direction[i].x)
    if (0..<m).contains(nP.y) &&
        (0..<n).contains(nP.x) &&
        map[start.y][start.x] > map[nP.y][nP.x] {
      if dp[nP.y][nP.x] > 0 {
        dp[start.y][start.x] += dp[nP.y][nP.x]
      } else if dp[nP.y][nP.x] == 0 {
        dp[start.y][start.x] += dfs(start: nP)
      }
    }
  }
  if dp[start.y][start.x] == 0 {
    dp[start.y][start.x] = -1
    return 0
  } else {
    return dp[start.y][start.x]
  }
}

let result = dfs(start: (0, 0))
print(result == -1 ? 0 : result)