[백준 1520] 내리막길

https://www.acmicpc.net/problem/1520

1520번: 내리막 길

---

접근

출발지에서 도착지까지 문제에서 주어진 조건에 부합하는 경로의 개수를 구해야한다. 이를 위해 DFS를 활용하였다. 출발지에서부터 상하좌우를 탐색하여 현재 위치보다 낮은 위치로 재귀호출을 진행하였다. 이때 현재 위치가 도착지일 때는 도착지까지 올 수 있는 경우의 수를 증가하였다.

 

하지만 DFS만을 이용하여 풀 때는 답은 정확하게 출력될 수 있지만 이미 가봤던 경로도 계속해서 탐색을 진행하기 때문에 시간 초과가 발생하였다. 예를 들어 A -> B -> C -> E까지 갔을 때 안되는 것을 확인하였는데 A -> B -> D -> E의 경로로 이동하여 또 안되는 것을 확인하고 돌아오게 된다.

 

따라서 도착지에서부터 출발지까지 돌아올 때 해당 위치까지 갈 수 있는 경우의 수를 더해나가 최종적으로 출발지에 모든 경우의 수가 담기도록 한다.

 

DP를 공부하고있는데 더 이해를 해보고 다시 작성해야겠다.

 

구현

• 문제에서 주어지는 입력을 받는다.
• 이후 memo라는 2차원 리스트를 -1로 초기화한다.
• -1일 때는 아직 방문하지 않은 위치이며 0일 때는 현재 위치까지 도달할 경우의 수가 없다는 것을 의미하고 1이상은 도달할 수 있는 경우의 수를 의미한다.

M, N = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(M)]
memo = [[0 for _ in range(N)] for _ in range(M)]

 

• (0, 0)에서 출발한다.
• 일단 현재 위치를 0으로 표시한다.
• 이후 재귀호출로 다음 위치를 탐색하닥 도착지에 도달했을 때 1을 반환한다.
• 이후 출발지로 돌아오면서 모든 경우의 수를 더해나간다.

def dfs(y, x):
    # 출발지에서 도착지까지 도달했을 경우에는 1을 반환하도록 한다.
    if y == M-1 and x == N-1:
        return 1
    if memo[y][x] != -1:
        return memo[y][x]

    memo[y][x] = 0
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if check_range(ny, nx):
            if board[y][x] > board[ny][nx]:
                memo[y][x] += dfs(ny, nx)

    return memo[y][x]

---

전체 코드

def check_range(y, x):
    return (0 <= y < M) and (0 <= x < N)

def dfs(y, x):
    # 출발지에서 도착지까지 도달했을 경우에는 1을 반환하도록 한다.
    if y == M-1 and x == N-1:
        return 1
    if memo[y][x] != -1:
        return memo[y][x]

    memo[y][x] = 0
    for d in range(4):
        ny = y + dy[d]
        nx = x + dx[d]
        if check_range(ny, nx):
            if board[y][x] > board[ny][nx]:
                memo[y][x] += dfs(ny, nx)

    return memo[y][x]

M, N = map(int, input().split())
board = [list(map(int, input().split())) for _ in range(M)]
memo = [[0 for _ in range(N)] for _ in range(M)]

dy = [1, -1, 0, 0]
dx = [0, 0, 1, -1]

print(dfs(0, 0))