[baekjoon] 백준 1520번(파이썬): 내리막 길

문제

1520번: 내리막 길

알고리즘

- dfs 탐색과 dp를 통해 문제를 수행한다.

- dp 배열에 모든 칸에 초기값을 -1로 초기화한다.

- 각 칸을 탐색 시 0으로 초기화해주어 탐색 유무를 판단하고 목적지까지 도착하면 1을 리턴 받는다.

- dp값이 -1이라면 탐색하지 않은 곳으로 탐색한다.

- dp값이 0이라면 탐색한 곳이지만 그 후에 탐색할 곳이 없는 칸이 된다.

- dp값이 1 이상의 값이라면 이전에 도착지까지 방문한 값으로 dp값을 리턴 받아 다시는 그 경로를 탐색하지 않게 한다.

- 시작점의 dp값을 출력하여 모든 경로의 개수를 확인한다.

코드

import sys
sys.setrecursionlimit(10 ** 9)


# dfs 탐색
def dfs(x, y):

    # 목적지에 도착했으면 1을 리턴하여 목적지까지 이동한 칸 모든 칸에 1을 더한다.
    if x == m - 1 and y == n - 1:
        return 1

    # 탐색하지 않은 곳이라면 탐색
    if dp[x][y] == -1:
        dp[x][y] = 0 # 탐색 유무

        # 상/하/좌/우 탐색
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]

            # 범위 내에 있고 현재 높이보다 낮은 높이라면
            if 0 <= nx < m and 0 <= ny < n:
                if graph[x][y] > graph[nx][ny]:
                    dp[x][y] += dfs(nx, ny) # (x, y)칸까지 몇번 이동하는지

    # 탐색한 곳이거나 탐색할 수 없는 곳이라면 자기 자신을 리턴
    # 마지막에는 (0, 0)을 리턴
    return dp[x][y]


m, n = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
dp = [[-1 for _ in range(n)] for _ in range(m)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
print(dfs(0, 0))

 

실패한 코드(16%.. 시간 초과)

import sys
sys.setrecursionlimit(10 ** 9)

def dfs(x, y):

    if x == m - 1 and y == n - 1:
        cnt.append(1)
        return

    for i in range(4):
        nx = x + dx[i]
        ny = y + dy[i]

        if 0 <= nx < m and 0 <= ny < n:
            if graph[x][y] > graph[nx][ny]:
                dfs(nx, ny)


m, n = map(int, sys.stdin.readline().split())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
dx = [1, -1, 0, 0]
dy = [0, 0, 1, -1]
cnt = []
dfs(0, 0)
print(len(cnt))

dfs 탐색을 통해서만 문제를 수행했는데 dfs 탐색으로만 문제를 수행하게 되면 이미 탐색한 곳을 다시 한번 탐색하게 되면서 시간 초과가 나오게 된다. 그렇다고 해서 탐색 한 곳을 탐색 처리하게 되면 탐색한 곳은 다시 방문하지 않아 문제를 풀 수가 없게 된다. 따라서 dp를 통해 모든 칸에 초기값을 -1로 초기화하고 탐색 시 0으로 다시 초기화해주어 탐색한다. dp 값이 1 이상의 값이라면 이전에 도착지까지 방문한 값으로, dp값을 리턴 받아 그 경로를 탐색하지 않고 다른 곳을 탐색한다. 결국 탐색한 곳은 다시 탐색하지 않고 수를 리턴 받기 때문에 시간 복잡도가 줄게 되고 출발지부터 목적지까지 이동한 칸을 확인할 수 있다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법