[백준/Swift] 1520 내리막길

문제

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

1520번: 내리막 길

 

시간초과 코드

import Foundation

let input = readLine()!.split(separator:" ").map { Int($0)! }
let m = input[0], n = input[1]   //m: x / n : y
var board:[[Int]] = []
for _ in 0..<m {
  board.append(readLine()!.split(separator:" ").map { Int($0)! })
}

let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

var ny = 0, nx = 0
var answer = 0

func dfs(_ x: Int, _ y: Int) {
    if x == m-1 && y == n-1 {
        answer += 1
        return
    }
  
    for i in 0..<4 { // 상하좌우로 탐색 -> DFS
      nx = x + dx[i]
      ny = y + dy[i]

      guard 0..<m ~= nx && 0..<n ~= ny else { continue }

      if board[x][y] > board[nx][ny] {
        dfs(nx, ny)
      }
    }
}

dfs(0, 0)
print(answer)

시간초과가 나는 이유

- 보드의 가로, 세로 길이가 최대 500, 500 인데 최악의 경우에는 상하좌우를 25000칸씩 탐색하므로, 4^25000 = 수가 어마어마하므로 시간초과가 날 수 있는 코드이다.

- 시간초과를 줄이려면? -> 값을 저장하고 있어야함 -> DP의 메모이제이션 기법 활용

예를들어 이 경우를 비교해보면 20에서 도착지점까지 가는 경우가 동일하므로, 이 구간을 새로 계산할 필요가 없이 저장해두면 된다.

 

통과 코드

import Foundation

let input = readLine()!.split(separator:" ").map { Int($0)! }
let m = input[0], n = input[1]   //m: x / n : y
var board:[[Int]] = []
for _ in 0..<m {
  board.append(readLine()!.split(separator:" ").map { Int($0)! })
}
var dp = Array(repeating: Array(repeating: -1, count: n), count:m)
//오답노트 1.
//dp와 board혹은 visited와 board를 활용하여 같이 탐색하는 형태일 때, index error를 방지하기 위해 2개의 수의 행 x 열을 반드시 동일하게 맞춰줄것

//오답노트 2.
// 초기값을 0이 아니라 -1로 지정하는 이유?
// dp는 메모이제이션을 위해서 존재하는데, 경로의 수가 0인 경우도 존재하므로, 27번째 줄에서 0이 아닌것으로 조건을 주면 중복적으로 탐색하는 것과 같게됨

let dx = [-1, 1, 0, 0]
let dy = [0, 0, -1, 1]

var ny = 0, nx = 0

func dfs(_ x: Int, _ y: Int) -> Int {
    if x == m-1 && y == n-1 {  // 도착하면 경우의 수 + 1 추가니까 return 1
        return 1
    }
    
    if dp[x][y] != -1 {  // 탐색 중복 제거
        return dp[x][y]  // 이미 계산한 경로의 수는 계산할 필요가 없으므로, 자기자신의 값 return
    }

    dp[x][y] = 0
  // 오답노트 3. 0으로 초기화하는 이유? -> 방문 여부 체크 (나중에 중복적으로 탐색하지 않게 하기 위함)
  // 경로의 수가 0일수도 있고, 이후에 경로가 있다면 여기에 더해줘야 하므로 0으로 초기화
  
    for i in 0..<4 { // 상하좌우로 탐색
      nx = x + dx[i]
      ny = y + dy[i]

      guard 0..<m ~= nx && 0..<n ~= ny else { continue }

      if board[x][y] > board[nx][ny] {
        dp[x][y] += dfs(nx, ny)
      }
    }
    
    return dp[x][y]
}

print(dfs(0, 0))
print(dp)

1) DP 테이블을 어떻게 정의하고, 어떤 값을 저장하고 있어야하는가?

dp[i][j] -> i와 j에서 도착지점 (m-1, n-1)까지 가는 경우의 수

이 값이 구해지면, 이를 중복적으로 계산할 필요가 없어지므로 해당 내용을 저장해둠

 

2) DP의 초기값을 0이 아니라 -1로 하는 이유가 무엇일까?

- 0으로 하게되면, 도착지점까지의 경로가 0인건지 방문을 안한건지 필터링이 안되므로 연산의 중복을 제거하지 않는 것과 같음.

- 따라서 -1로 초기화해두고, 방문할 때마다 0으로 초기화한 뒤 for문을 통해 상하좌우 탐색의 경우의 수를 더해줌

- 만약 -1이 아니라면, 이미 탐색을 했다는 것이으므로 해당 탐색의 값을 그대로 가져오면서 return하면 됨

 

그리고 도착 지점에 도착했을 때에는 경우의 수 + 1 이므로 해당 값을 가지고 return 시켜서 시작 지점에 더해주기 위해

아래와 같이 도착지점의 좌표일 때 return 1을 해준다.

    if x == m-1 && y == n-1 {  // 도착하면 경우의 수 + 1 추가니까 return 1
        return 1
    }

 

해당 코드를 그림으로 잘 그려주신 블로거분이 있어서 링크를 첨부해두겠다.

https://velog.io/@jxlhe46/%EB%B0%B1%EC%A4%80-1520%EB%B2%88.-%EB%82%B4%EB%A6%AC%EB%A7%89%EA%B8%B8

 

reference

https://simsimjae.tistory.com/23