문제
접근
DFS와 DP를 이용하여 해결했다.
기본 아이디어는 재귀를 이용한 DFS이다.
여기까진 DFS에 대한 지식만 있다면 쉽게 생각해내고 구현할 수 있다.
0, 0 에서 시작해서 상하좌우 가능한 경로를 재귀적으로 수행하며, 최종 목적지에 도착하면 1을 리턴한다.
하지만 이 경우 board의 크기가 크기 때문에 재귀 스택이 매우 커지며, 시간초과가 날 수 있다.
따라서 visited 배열을 단순히 방문 표시가 아닌 해당 좌표에서 목적지까지 가능한 경우의 수를 입력해주고, 이미 방문한 위치이면 해당 값을 리턴해준다.
코드
- 파이썬 코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 6)
n = 0
m = 0
dx = [0, 0, 1, -1]
dy = [1, -1, 0, 0]
def dfs(x, y, board, visited):
if x == n-1 and y == m-1:
return 1
if visited[y][x] != -1:
return visited[y][x]
visited[y][x] = 0
for tx, ty in zip(dx, dy):
nx = x + tx
ny = y + ty
if nx < 0 or nx >= n or ny < 0 or ny >= m:
continue
if board[ny][nx] < board[y][x]:
visited[y][x] += dfs(nx, ny, board, visited)
return visited[y][x]
def main():
global n, m
m, n = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(m)]
visited = [[-1] * n for _ in range(m)]
print(dfs(0, 0, board, visited))
if __name__ == "__main__":
main()