[백준/BOJ] 1520번 내리막 길(Swift)

문제 난이도: 골드 3

 

사용 알고리즘: DFS, DP

 

M,N은 각각 500 이하이고 최대 250,000까지 연산이 필요하다.

제한 시간은 2초이므로 200,000,000번(2억번)의 연산이 넘어가게 되면 시간초과가 된다.

 

대충 O(N^4)을 넘지 않으면 시간초과는 뜨지 않는다.

 

첫번째 풀이는 DFS에 백트래킹을 적용해서 문제풀이를 진행했다.

다만 백트래킹을 적용하게 되면 셀의 모든 방향에 대하여 재귀 호출이 발생하여 시간초과가 뜬다.

import Foundation

let size = readLine()!.split(separator: " ").map { Int($0)! }
let y = size[0]
let x = size[1]
var map: [[Int]] = []
var visited = Array(repeating: (Array(repeating: false, count: x)), count: y)
let directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]

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

func dfs(pointX: Int, pointY: Int, cur: Int) -> Int {
    
    var route = 0
    
    if pointX == x - 1 && pointY == y - 1 {
        return 1
    }
    
    for direction in directions {
        
        let newX = pointX + direction.0
        let newY = pointY + direction.1
        
        if newX < 0 || newX >= x || newY < 0 || newY >= y || visited[newY][newX] {
            continue
        }
        
        if cur > map[newY][newX] {
            
            visited[pointY][pointX] = true
            route += dfs(pointX: newX, pointY: newY, cur: map[newY][newX])
            visited[pointY][pointX] = false
        }
    }
    
    return route
}

print(dfs(pointX: 0, pointY: 0, cur: map[0][0]))

 

---

 

두 번째는 DFS와 DP를 사용하였다.

 

DP를 통해 이미 진행된 경로에 대해서 저장하여 반복되는 경우의 수를 줄였다.

 

pointX == x - 1

import Foundation

let size = readLine()!.split(separator: " ").map { Int($0)! }
let y = size[0]
let x = size[1]
var map: [[Int]] = []
let directions = [(0, -1), (0, 1), (-1, 0), (1, 0)]
var dp = Array(repeating: (Array(repeating: -1, count: x)), count: y)

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

func dfs(pointX: Int, pointY: Int) -> Int {
    
    // 목적지 도착
    if pointX == x - 1 && pointY == y - 1 {
        return 1
    }
    
    // 이미 계산된 경로라면 해당 경로의 결과값 반환
    if dp[pointY][pointX] != -1 {
        return dp[pointY][pointX]
    }
    
    dp[pointY][pointX] = 0
    
    // 현재 위치에서 갈 수 있는 모든 방향으로 DFS 탐색 진행
    for direction in directions {
        
        let newX = pointX + direction.0
        let newY = pointY + direction.1
        
        if newX >= 0 && newX < x && newY >= 0 && newY < y && map[pointY][pointX] > map[newY][newX] {
            // 해당 경로에 대한 탐색이 가능하다면 해당 경로로 가능한 경우의 수가 모두 저장
            dp[pointY][pointX] += dfs(pointX: newX, pointY: newY)
        }
    }
    
    return dp[pointY][pointX]
}

print(dfs(pointX: 0, pointY: 0))