📌 문제
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
📌 입력
첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.
📌 출력
첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.
📌 문제 풀이
👨🏫 접근
목적지에 도착할 수 있는 경로의 개수를 모두 찾아야 한다. 이때 목적지까지 도착하는 경우의 수가 매우 많아서 DP 테이블에 값을 저장해서 그래프를 탐색하도록 한다.
이미 값이 있는 곳은 그래프가 목적지까지 도착할 수 있는 것이기 때문에 값이 있다면 바로 값을 반환하여 추가적인 연산을 줄인다.
👨🏫 문제 풀이
📄 전체 코드
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
d = [[-1] * m for _ in range(n)]
d[-1][-1] = 1
def dfs(x, y):
if d[x][y] != -1:
return d[x][y]
d[x][y] = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if graph[x][y] > graph[nx][ny]:
d[x][y] += dfs(nx, ny)
return d[x][y]
print(dfs(0, 0))
📄 준비
import sys
sys.setrecursionlimit(10**6)
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]
n, m = map(int, input().split())
graph = [list(map(int, input().split())) for _ in range(n)]
d = [[-1] * m for _ in range(n)]
d[-1][-1] = 1
dp 테이블은 만들고, 아직 방문하지 않은 좌표는 -1로 처리해준다. 목적지까지 도착하지 못하는 경우가 있기 때문에 -1로 저장해둬야 한다.
📄 풀이
def dfs(x, y):
if d[x][y] != -1:
return d[x][y]
d[x][y] = 0
for i in range(4):
nx, ny = x + dx[i], y + dy[i]
if 0 <= nx < n and 0 <= ny < m:
if graph[x][y] > graph[nx][ny]:
d[x][y] += dfs(nx, ny)
return d[x][y]
print(dfs(0, 0))
이하의 과정은 보통의 dfs와 같다.
📌 총평
어려웠다. DFS와 DP를 섞은 문제라서 응용할 때 비슷하게 활용해봐야겠다.
'Algorithm > Dynamic Programming' 카테고리의 다른 글
[Python - Dynamic Programming] 9084 동전 (2) | 2022.09.20 |
---|---|
[Python - Dynamic Programming] 1699 제곱수의 합 (2) | 2022.09.20 |
[Python - Dynamic Programming] 9252 LCS 2 (0) | 2022.08.31 |
[Python - Dynamic Programming] 9251 LCS (0) | 2022.08.31 |
[Python - Dynamic Programming] 11052 카드 구매하기 (0) | 2022.08.31 |