[python 파이썬] 백준 1520번 내리막 길

DP 좋은 문제 추천

https://won-percent.tistory.com/entry/%EC%A2%8B%EC%9D%80-DP-%EB%AC%B8%EC%A0%9C%EB%93%A4-%EC%B6%94%EC%B2%9C

문제

https://www.acmicpc.net/problem/1520

풀이

이틀 걸려서 이 풀이 저 풀이 보면서 이해하려했던 문제이다. dfs 문제 풀이에 대해선 전혀 몰랐기 때문에 dp + dfs 인 이 문제를 혼자서 푸는건 불가능했을거라고 위로중. 일단 풀긴풀었는데 다음에 다시 보면 모를것 같으니까 다음에 다시 풀어볼 예정이다. 

지금껏 놀았으니 힘든건 당연한거라 생각하고 공부해야겠다. 

import sys

def dfs(i,j,m,n):
 if result[i][j] == 1 : # 이미 방문함
 return
 result[i][j]=0

 if i>0 and MAP[i-1][j] > MAP[i][j]: # up
 if result[i-1][j] == -1:
 dfs(i-1,j,m,n)
 result[i][j] += result[i-1][j]
 if i < m-1 and MAP[i+1][j] > MAP[i][j]: #down
 if result[i+1][j] == -1:
 dfs(i+1,j,m,n)
 result[i][j] += result[i+1][j]
 if j>0 and MAP[i][j-1] > MAP[i][j]: #left
 if result[i][j-1] == -1:
 dfs(i,j-1,m,n)
 result[i][j] += result[i][j-1]

 if j < n-1 and MAP[i][j+1] > MAP[i][j]: # right
 if result[i][j+1] == -1:
 dfs(i,j+1,m,n)
 result[i][j] += result[i][j+1]

m, n = map(int, sys.stdin.readline().split())
MAP = [[0 for _ in range(n)] for _ in range(m)]
result = [[-1 for _ in range(n)] for _ in range(m)]

for i in range(m):
 MAP[i] = list(map(int, sys.stdin.readline().split()))

result[0][0] = 1

for i in range(m):
 for j in range(n):
 dfs(i,j,m,n)

print(result[-1][-1])

2020.08.08

제대로 이해 못한것도 걸리고 풀이가 총 2가지가 있는 것 같아서 다른 풀이도 가져왔다. 

위에 풀이는 모든 dfs 경우를 다 구하는건데 이번에 푼 풀이는 재귀를 이용해서 런타임을 줄였다.

이번 것도 솔직히 처음 푸는 재귀, dfs라서 제대로 이해는 못했지만 여러번 보니 대충 느낌은 온다.

아 중요한건 python 에서 dfs 재귀로 풀땐

 import sys

 sys.setrecursionlimit(10**9)

이걸 꼭 넣어줘야한다고한다. 안넣으면 런타임 오류 뜨더라.

방문할때마다 -1 에서 0으로 바꿔주고 상하좌우에 높이 낮은놈이 있으면 거기로 가는것! 그러다보면 언젠간 끝에 도달할것이고 그 말은 처음부터 끝까지 왔던 경로 1개 찾은거니까 dp[m-1][n-1] = 1으로 바꿔준다.

그리고 다시 되돌아가면서 그동안 지나쳤던 재귀 안의 계산을 해주는,,,,,(재귀...(재귀(....재귀(.....재귀....(....재귀))))) 이런 느낌? 어쨌든 그래서 처음 자리로 돌아오면 계산이 완료가 되었을것이다. 

print 는 처음 dfs(0,0) 을 하거나 dp[m-1][n-1] 을 하면 그게 답. 

이해못할만한 설명은 각설하고 코드 

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**9)
m,n = map(int,input().split())
MAP = [list(map(int, input().split())) for _ in range(m)]
dp = [[-1 for _ in range(n)] for _ in range(m)]
dp[m-1][n-1] = 1

def dfs(x,y):

 if dp[x][y] == -1: #방문하지않음
 dp[x][y] = 0 #방문으로표시
 for dx, dy in (1,0),(-1,0),(0,1),(0,-1):
 if 0<=x+dx<m and 0<=y+dy<n and MAP[x][y]>MAP[x+dx][y+dy]:
 dp[x][y] += dfs(x+dx,y+dy)
 return dp[x][y]

print(dfs(0,0))