반응형
문제 풀이
dp와 dfs를 함께 사용해야하는 문제이다.
1. dp 배열에 해당 칸을 방문한 적이 없으면 -1, 있으면 해당 칸부터 (0,0)까지 갈 수 있는 현재까지 발견한 경로의 수를 담는다.
2. 위의 dp 배열과 지도를 기반으로 dfs를 진행한다.
2-1) 이동 가능한 칸의 dp값이 -1이라면 방문한다.
2-2) 이동 가능한 칸의 dp값이 0이라면 방문하지 않는다. 해당 칸에서는 (0,0)까지 갈 수 없다.
2-3) 이동 가능한 칸의 dp값이 1이상이라면 현재 칸의 dp값에 이동 가능한 칸의 dp값을 더해준다. 현재 칸에서 (0,0)까지 갈 수 있는 방법의 수는, 현재 칸에서 이동할 수 있는 칸들에서부터 (0,0)까지 갈 수 있는 경로의 합이다.
Python Code
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
|
import sys
sys.setrecursionlimit(10000)
# 0: 상, 1: 좌, 2: 하, 3: 우
a = [0,-1,0,1]
b = [-1,0,1,0]
def dfs(x,y):
if dp[y][x] == -1 :
dp[y][x] = 0
if x<0 or x>n-1 or y<0 or y>m-1: return 0
for i in range(4):
nx = x + a[i]
ny = y + b[i]
if (0 <= nx <= n-1 and 0 <= ny <= m-1) and maps[ny][nx] > maps[y][x] :
if dp[ny][nx] > 0:
dp[y][x] += dp[ny][nx]
# 방문한 적 없으면 dfs
elif dp[ny][nx] == -1 :
dp[y][x] += dfs(nx,ny)
return dp[y][x]
if __name__ == '__main__':
m,n = map(int,sys.stdin.readline().split())
maps = [list(map(int, sys.stdin.readline().split())) for _ in range(m)]
dp = [[-1] * n for _ in range(m)]
dp[0][0] = 1
dfs(n-1,m-1)
print(dp[-1][-1])
|
cs |
Line 9 : 지도를 벗어나면 0을 반환한다.
Line 13 : 새로운 좌표가 지도를 벗어나지 않으며 이동가능하면, 새로운 좌표를 dfs하거나(Line 17, 과정 2-2) 현재 칸의 dp 값에 새로운 좌표의 dp값을 더해준다(Line 14, 과정 2-3).
문제 링크
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으�
www.acmicpc.net
반응형
'알고리즘 > 백준' 카테고리의 다른 글
| 백준 11057 오르막 수 Python (0) | 2020.12.03 |
|---|---|
| 백준 4358 생태학 (0) | 2020.10.21 |
| 백준 1152 단어의 개수 (0) | 2020.08.31 |
| 백준 2884 알람 시계 (0) | 2020.05.08 |
| 백준 9465 스티커 (0) | 2020.04.18 |