백준: 1520 내리막길

문제

1520번: 내리막 길

 

문제 풀이

 (0, 0)에서 출발하여, (m - 1, n - 1)에 도착하는 경우의 수를 구하는 문제이다. 문제의 조건은 더 낮은 지점으로만 이동할 수 있으며, 가능한 경우의 수를 모두 구하여야 한다. 이 문제를 풀기 위해 단순히 BFS, DFS를 사용하면 각 경로를 탐색하기 위해 중복으로 탐색할 가능성이 크다.

 

 따라서, 재귀 호출을 통해서 방문 가능한 경로의 수를 반환하고, 한번 탐색한 경로는 더 이상 탐색하지 않도록 하는 방법을 사용하여야 시간 초과를 발생시키지 않고 문제를 해결할 수 있다.

 

 예제 입력 1은 위의 그림과 같이 3가지의 경로 진행될 수 있다. 이를 계산 하기 위해 dfs를 통해 (m - 1, n - 1)까지 탐색한 후에, 값을 return 해주는 방식을 사용하면 오른쪽 아래 끝부터 값이 올라오게 될 것이다. 따라서 이를 중첩해주면 3이라는 결과를 찾을 수 있다.

 

코드

from sys import stdin


def visitable(x, y):
    return 0 <= x < m and 0 <= y < n


def dfs(x, y):
    if x == m - 1 and y == n - 1:
        return 1

    if visited[x][y] == -1:
        visited[x][y] = 0

        for dx, dy in dirs:
            next_x, next_y = x + dx, y + dy

            if visitable(next_x, next_y):
                if graph[next_x][next_y] < graph[x][y]:
                    visited[x][y] += dfs(next_x, next_y)

    return visited[x][y]


if __name__ == '__main__':
    dirs = ((0, 1), (0, -1), (1, 0), (-1, 0))
    m, n = map(int, stdin.readline().split())
    graph = [list(map(int, stdin.readline().split())) for _ in range(m)]
    visited = [[-1] * n for _ in range(m)]

    print(dfs(0, 0))