https://www.acmicpc.net/problem/1520
시간 2초, 메모리 128MB
input :
- h, w (1 <= h, w <= 500)
- 각 지점의 높이가 입력 된다.(1 <= 지점의 높이 <= 10000)
output :
- 이동 가능한 경로의 수 h를 출력.
조건 :
- 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
- 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다.
처음에도 도착지점부터 가능 한 경로들을 모두 합해야 겠다. 라는 생각으로 시작을 했지만 이 경로에 대한 생각이 잘못 되었다.
경로를 찾으려면 이 값들을 계속 타고 들어간 후에 경로가 맞다는 표시를 하여야 하는데. 이를 하지 않고 이동이 가능한지만 판단을 했기 떄문에 답을 구할 수 없었다.
그렇다면 값들을 어떻게 계속 타고 들어가는가? dfs를 이용하자.
어차피 우리는 도착점까지 오는 모든 경로를 찾고 싶다. 그렇다면 이는 visit배열에서 상, 좌로 이동해서 오는 경로를 나타내는 것이다.
고로 이를 dfs 수행한다.
그리고 이미 방문을 한 지점도 존재를 한다.
이미 방문을 한 지점들의 경로는 이미 계산을 했기 때문에 이것은 visit 배열에서 꺼내서 쓰도록 하자.
그래서 이 문제를 DP로 분류 한것 같다.
import sys
def dfs(x, y):
if x == 0 and y == 0:
return 1
# 방문을 하지 않은 점에 대해서 dfs를 수행한다.
if visit[x][y] == -1:
visit[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx >= h or nx < 0 or ny >= w or ny < 0:
continue
# 처음부터 내가 찾으려 한 값은 [h][w]에 올 수 있는 모든 경로를
# 기록한 후에 이를 더해서 찾으려 하였다.
# 그렇다면 이것을 어떻게 해야 하는가 가능 한 경로들을 각 위치에 저장
# 하도록 해 주는 것이 바람직하다.
# 그렇기 때문에 각 위치 x, y 에서 nx, ny로 이동을 할 수 있다면
# 그 위치까지 올 수 있는 경로를 다 더해 주기 위해
# 아래 에서 처럼 dfs를 수행하고 이를 visit에 저장하는 것이다.
if data[nx][ny] > data[x][y]:
visit[x][y] += dfs(nx, ny)
# 이미 방문을 한 지점이라면 그냥 return 해준다.
return visit[x][y]
h, w = map(int, sys.stdin.readline().split())
data = []
for i in range(h):
temp = list(map(int, sys.stdin.readline().split()))
data.append(temp)
visit = [[-1] * w for i in range(h)]
dx = [-1, 1, 0, 0]
dy = [0, 0, 1, -1]
print(dfs(h - 1, w - 1))
