[ 코딩테스트/백준 ]
[백준/BOJ] 1520번 내리막 길(Swift)
2024-08-18 21:22:15
문제 난이도: 골드 3 사용 알고리즘: DFS, DP M,N은 각각 500 이하이고 최대 250,000까지 연산이 필요하다.제한 시간은 2초이므로 200,000,000번(2억번)의 연산이 넘어가게 되면 시간초과가 된다. 대충 O(N^4)을 넘지 않으면 시간초과는 뜨지 않는다. 첫번째 풀이는 DFS에 백트래킹을 적용해서 문제풀이를 진행했다.다만 백트래킹을 적용하게 되면 셀의 모든 방향에 대하여 재귀 호출이 발생하여 시간초과가 뜬다.import Foundationlet size = readLine()!.split(separator: " ").map { Int($0)! }let y = size[0]let x = size[1]var map: [[Int]] = []var visited = Array(repeati..