코드

import sys
sys.setrecursionlimit(10 ** 8)

m, n = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(m)]

# dp 테이블의 의미
# dp[x][y] : x, y에서 출발하여 dp[m][n]까지 도달할 수 있는 경우의 수
# 0으로 초기화하면 시간 초과가 발생
dp = [[-1 for _ in range(n)] for _ in range(m)]

# dfs 함수 내부에서 선언하면
# 반복적으로 아래 리스트가 생성되므로 그냥 밖에서 선언
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

def dfs(x, y):

    # 도착 지점까지 도달하면 1 반환 => 경우의 수가 1 증가
    if x == m-1 and y == n-1:
        return 1
    
    # 이미 방문한 적이 있다면
    # 해당 위치에서의 경우의 수를 반환
    # 이 DP 테이블을 이용하여 소요 시간을 줄일 수 있음
    if dp[x][y] != -1:
        return dp[x][y]
    
    # dfs를 수행할 때
    # 방문한 적도 없고, 마지막 지점이도 아니라면
    # 경우의 수를 0으로 초기화시킴
    dp[x][y] = 0
    
    # 4방향으로 전진
    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]
        
        # 그래프를 벗어나면 반복 넘김
        if nx < 0 or nx >= m or ny < 0 or ny >= n:
            continue
            
        # 이전 좌표의 값이 더 큰 경우에만 fs를 수행 
        # 방문한 적이 있는 경우 또는
        # 최종 목적지까지 도착하는 경우
        # 위의 두 경우의 누적합을 dp[x][y]에 저장
        if graph[x][y] > graph[nx][ny]:
            dp[x][y] += dfs(nx, ny)
            
    return dp[x][y]

print(dfs(0, 0))

문제 해설

DFS와 DP 테이블을 함께 사용하여 해결할 수 있는 문제.

DFS로만 접근하기엔 주어지는 경우의 수가 너무 많은 문제였다. 결국 자연스럽게 DP를 떠올리게 됐으나, 어떤 식으로 연계를 하여 풀 수 있는지 감을 찾지 못하여 구글링의 도움을 받았다.

문제 해결에 어려움을 느꼈던 부분은 아래와 같다.

  1. sys.setrecursionlimi을 10^6보다 낮게 하면 RecursionError가 발생함
  2. sys.setrecursionlimi을 10^9보다 높게하면 메모리 초과가 발생함
  3. DP 테이블의 초기값을 0으로 선언하면 시간 초과가 발생함
  4. DP 테이블의 값을 DFS 수행 시 마다 0으로 초기화 시키고 조건에 부합하는 경우에 누적하여 DP 테이블의 값을 업데이트 시킴
  5. 방문 이력이 있는 경우 (-1이 아닌 경우), DP 테이블의 값을 그대로 반환함

막상 코드를 짜는 과정 자체는 생각보다 수월했으나, 1, 2, 3번의 문제들 때문에 상당히 오래 시간을 잡아 먹었다 ㅠㅠ 이런 문제를 접할 때 마다 문제의 조건들을 더 세밀하게 파악할 수 있게 되는 것 같아서 뿌듯한 느낌도 있다. 더 많은 문제를 꾸준하게 접해봐야겠다.

댓글남기기

참고