1520 내리막 길
-
백준 1520 내리막 길Algorithm/BOJ 2021. 3. 30. 14:00
출처: www.acmicpc.net/problem/1520 분류: DP, DFS 접근방식 DFS 방식으로 원하는 칸에 도달하는 경로를 찾아나갈 수 있습니다. 대신 모든 경우를 탐색하면 시간제한에 걸리게 되므로 DP를 활용해야 합니다. 현재 칸에서 가능한 경우의 수는 이미 모두 탐색을 했기 때문에 방문한 칸을 다시 방문할 필요는 없고 저장된 방문 횟수만 가져옵니다. 구체적으로는 처음에 DP 배열에 -1을 넣어두고 방문하면 0으로 초기화하고 값을 더해줍니다. DP가 -1일 경우에만 탐색하고 아니면 DP의 값만 리턴합니다. 해결방법 typealias Point = (r: Int, c: Int) let rc = readLine()!.split(separator: " ").map { Int(String($0))!..