백준 / 내리막 길 / 1520번 / Python

*문제 출처는 백준에 있습니다.

문제 제목: 내리막 길 / 1520번 (골드 3단계)

문제 사이트: https://www.acmicpc.net/problem/1520

 

문제 설명

---

나의 풀이

1번은 시작점을 기준 아래쪽으로 쭉 내려가다 높이 15의 배열을 밟고 제일 오른 쪽 아래 지점으로 이동하게 됩니다.

2번의 경우의 수에서는 45-37-32로 가다가 2-1과 2-2로 나뉘게 됩니다.

2-1번에선 32-20-17-15를 밟게 되는데 이때 1번에서 높이 15를 밟게되면 들어갈 수 있다는 기록이 있으므로 들어가지 않더라도 카운트 합니다.

2-2번에서도 32-30-25-20를 밟게 되는데 2-1에서 높이 20을 밟으면 높이 15로 이어지고 높이 15는 제일 오른 쪽 아래 지점으로 이동할 수 있습니다.

이렇게 중복되는 길을 반복하지 않고 최소한의 값으로 이동하는 풀이를 사용했습니다.

DP를 이용했지만 중복되는 길을 반복하는 풀이

# dfs, DP 이용한 풀이

def dfs(graph, start, visited):
    qy, qx = start
    # 재귀함수가 아닌 스택을 이용한 dfs
    stack = [[qy, qx]]

    move = [(0, 1), (0, -1), (1, 0), (-1, 0)]

    while stack:
        iy, ix = stack.pop()
        # 현재 위치를 저장할 변수
        current = graph[iy][ix]

        for ny, nx in move:
            y = iy + ny
            x = ix + nx
            next_value = 1e9
            if 0 <= y < len(graph) and 0 <= x < len(graph[0]):
                next_value = graph[y][x]
            if 0 <= y < len(graph) and 0 <= x < len(graph[0]) and current > next_value:
                visited[y][x] += 1
                stack.append((y, x))

    return visited[len(graph) - 1][len(graph[0]) - 1]

# n, m를 입력 받는 변수
n, m = map(int, input().split())

# graph: 지도
graph = []

# 방문한 곳 체크
visit = [[0] * m for _ in range(n)]

for _ in range(n):
    line = list(map(int, input().split()))
    graph.append(line)

print(dfs(graph, [0, 0], visit))

정답 코드: DP를 이용하여 중복되는 길을 제외하는 풀이

import sys

sys.setrecursionlimit(10 ** 6)

# DFS + DP로 경로의 수를 계산하는 함수
def dfs(y, x, graph, dp):
    if y == len(graph) - 1 and x == len(graph[0]) - 1:
        return 1  # 목표 지점에 도착하면 경로 수 1 리턴

    if dp[y][x] != -1:  # 이미 계산된 경로가 있으면 그 값을 리턴
        return dp[y][x]

    # 상, 하, 좌, 우 이동
    move = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    dp[y][x] = 0  # 현재 위치에서 경로 수 초기화

    for dy, dx in move:
        ny, nx = y + dy, x + dx
        if 0 <= ny < len(graph) and 0 <= nx < len(graph[0]):
            if graph[y][x] > graph[ny][nx]:  # 내리막길 조건
                dp[y][x] += dfs(ny, nx, graph, dp)

    return dp[y][x]


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

# DP 테이블 (-1로 초기화)
dp = [[-1] * m for _ in range(n)]

# DFS 탐색 시작
print(dfs(0, 0, graph, dp))

---

※ 알아야 할 것

https://newkimjiwon.tistory.com/81

[Algorithm] 깊이 우선 탐색(DFS, Depth-First Search)