Hanbit the Developer
[Python] 백준 1520번: 내리막 길 본문
https://www.acmicpc.net/problem/1520
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
def dfs(x, y):
# 이미 방문한 적이 있을 경우
if dp[x][y] != -1:
return dp[x][y]
# Base case
if x == M-1 and y == N-1:
return 1
# Recursive case
dp[x][y] = 0
for i in range(4):
nextX, nextY = x + dx[i], y + dy[i]
if 0 <= nextX <= M-1 and 0 <= nextY <= N-1:
if nums[x][y] > nums[nextX][nextY]:
dp[x][y] += dfs(nextX, nextY)
return dp[x][y]
if __name__ == '__main__':
M, N = map(int, input().split())
nums = [list(map(int, input().split())) for _ in range(M)]
dp = [[-1]*N for _ in range(M)]
print(dfs(0, 0))
DFS + DP로 풀었다.
DP[x][y]는 (x, y)에서 도달할 수 있는 경로이다. 즉, 우리는 DP[0][0]을 위해 코드를 작성한다.
DP는 모두 -1로 초기화하며, -1의 의미는 아직 방문하지 않은 것이다.
탐색 함수를 짤 때, 이것을 기준으로 방문한 적이 있을 경우에는 네 방향에 대한 탐색을 하는 것이 아니라, dp를 반환해준다.
아무튼, DFS의 구조가 꽤 간단하다. Base case는 x, y가 우측 하단인 경우이다.
그리고 Recursive case는, 내리막 길이라는 조건에 따라, 현재 좌표(x, y)에 대해 탐색을 해준다. 각 방향에 대한 경로의 경우의 수를 모아서 리턴해주는 식이다. 이렇게 하면 DP[0][0]이 우리가 원하는 값이 나온다.
여담이지만, 백준 온라인 저지에서 200문제를 해결하게 되었다.
'Algorithm > 백준' 카테고리의 다른 글
[Python] 백준 1647번: 도시 분할 계획 (0) | 2021.08.19 |
---|---|
[Python] 백준 14890번: 경사로 (0) | 2021.08.17 |
[Python] 백준 1509번: 팰린드롬 분할 (0) | 2021.08.15 |
[Python] 백준 4386번: 별자리 만들기 (0) | 2021.08.12 |
[Python] 백준 1007번: 벡터 매칭 (0) | 2021.08.11 |