문제
👀 문제 사이트 : https://www.acmicpc.net/problem/1520
풀이
난이도 : Gold III
이 문제는 직사각형 모양의 배열을 탐색하는 문제이다. 왼쪽 위 모서리에서 시작하여 오른쪽 아래 모서리에 도착하면 되는데, 일반적인 탐색과 달리 탐색할 때 값이 더 작은 곳으로만 탐색할 수 있다.
처음에는 일반적인 DFS로 진행하였다가 시간 초과가 발생하여 DP를 도입하였다. 한 번 방문한 곳은 다시 방문할 필요가 없기 때문이다. 또한 DP는 탑다운 방식을 사용하여 재귀적으로 빠져나올 때마다 DP의 값을 채워주었다.
- [x, y] : 현재 좌표
- [nx, ny] : 방문하고자 하는 좌표
- DP의 -1 : 전체적으로 한 번도 방문하지 않았다는 뜻
- DP의 0 : 전체적으로 방문은 했지만, 목적지에 도착하는 경로가 없다는 뜻
- DP의 값 x : 목적지에 도착하는 경로가 x번 있다는 뜻
- visited : 현재 진행하고 있는 DFS에서 방문한 곳을 표시
1) 처음 DP는 -1로 초기화해준다.
2) DFS로 들어오면 dp의 값을 0으로 만들어준다.
3) 상, 하, 좌, 우 방향을 탐색하여 DFS를 진행한다. [nx, ny]의 값이 [x, y]의 값보다 크거나 지금 진행하고 있는 DFS에서 방문했던 곳이라면 탐색을 진행하지 않는다.
4) 3번까지 통과하고, [nx,ny]의 dp값이 -1 이라면(한 번도 방문하지 않았다면) DFS를 진행하여 DP를 채워준다. (이미 dp의 값이 채워져있다면 아무것도 하지 않음)
5) dp[x][y]에 dp[nx][ny]값을 추가한다.
6) dfs 시작 시 x, y 가 목적지라면 dp[x][y] 를 1로 설정하고 return한다.
(이 부분을 통과하는 순간부터 dp의 값이 채워지기 시작하며, 탑다운 방식으로 dp의 값을 채운다.)
✔ 주의할 점
-
dp의 값을 -1이 아닌 0으로 초기화하고, -1과 0을 구분하지 않는 경우
-> 이미 방문을 했던 곳인데, dp의 값이 0으로 되어있으면 재탐색을 하여 시간초과가 발생한다.
-
python의 경우 dfs와 같이 재귀를 사용할 때, runtime error가 발생하는 경우가 있어
sys.setrecursionlimit을 통해 재귀 제한을 설정해주어야 한다.
코드
import sys
sys.setrecursionlimit(10**9)
n, m = map(int, input().split())
array = []
dp = [[-1] * m for _ in range(n)]
for _ in range(n):
array.append(list(map(int, input().split())))
dx = [0, 1, 0, -1]
dy = [1, 0, -1, 0]
def dfs(x, y, visited):
global n, m
dp[x][y] = 0
if x == n-1 and y == m-1:
dp[x][y] = 1
return
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if nx < 0 or ny < 0 or nx >= n or ny >= m:
continue
if visited[nx][ny] or array[nx][ny] >= array[x][y]:
continue
if dp[nx][ny] == -1:
visited[nx][ny] = True
dfs(nx, ny, visited)
visited[nx][ny] = False
dp[x][y] += dp[nx][ny]
visited = [[False] * m for _ in range(n)]
visited[0][0] = True
dfs(0, 0, visited)
print(dp[0][0])