1520. [Python]내리막길

1. 문제

 

 

2. 접근 방법

 

• 시간 제한: 1초
• 메모리 제한: 128MB
• 재귀
• DP
• 그래프 탐색

 

3. 파이썬 코드

 

import sys
# 재귀 제한 해제
sys.setrecursionlimit(100000)

input = sys.stdin.readline

N, M = map(int,input().split())

matrix = []
# 방문 체크
visited = [[-1] * M for _ in range(N)]

for _ in range(N):
    matrix.append(list(map(int,input().split())))

direction = [(0,-1),(-1,0),(0,1),(1,0)]
# 백트래킹
def backtracking(start):
    global cnt
    # 끝에 도달하면 1 리턴
    if start[0] == N-1 and start[1] == M-1:
        return 1
    # -1 외의 값인 경우 경로를 탐색한 적 있기 때문에 현재 위치값 리턴
    if visited[start[0]][start[1]] != -1:
        return visited[start[0]][start[1]]
    # 4방향 탐색한 값 저장
    road = 0
    # 4방향 탐색
    for k in range(4):
        ny = direction[k][0] + start[0]
        nx = direction[k][1] + start[1]
        # 조건에 만족하 경우 깊이 탐색 하며 리턴값 반환
        if 0 <= ny < N and 0 <= nx < M and matrix[ny][nx] < matrix[start[0]][start[1]]:
            road += backtracking((ny,nx))
    # 현재 위치에 경로 탐색을 통해 얻은 값 저장
    visited[start[0]][start[1]] = road
    # 현재 위치값 반환
    return visited[start[0]][start[1]]
# 끝에 도달하는 점 1로 갱신
visited[N-1][M-1] = 1
backtracking((0,0))
print(visited[0][0])

 

4. 문제를 풀고난 후 생각

 

• 욕심쟁이 판다와 비슷한 문제로 경로를 탐색하며 이미 탐색한 경로를 제거해주는 방법으로 접근해야 시간초과를 면할 수 있다.
• 처음에 간단히 DFS 돌리면 되는 문제인 줄 알고 접근했다가 시간초과를 고민했던 문제였다.
• 접근 방식이 재귀밖에 생각이 안나서 구현하며 리턴값을 어떻게 받아오는지 고민을 했고 다른 질문 게시판을 참조하여 문제를 접근할 수 있었다.
• 아직 알고리즘 접근 방식에 대해서 좀 더 공부해야할 것 같다는 생각이 듬

 

5. 문제를 푸는데 도움이 되는 지식

 

• 재귀
• 그래프 탐색
• DP