[백준] 1520. 내리막길 python

🐳 링크

백준 1520번 내리막길

🐕 문제

여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.

현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로가 가능하다.

지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
그림 출처: https://www.acmicpc.net/problem/1520

🐾 풀이 방법

• 경로의 개수를 누적합하는 visit라는 m*n배열을 -1로 초기화하여 생성해준다.
• dfs를 통해 마지막 좌표인 (m-1, n-1)부터 시작하여 (0,0)에 도달했을 때에 1을 리턴한다.
• dfs를 돌리기 시작한 좌표의 visit값에 해당 dfs의 리턴값의 합을 저장한다.

solution 코드

1. dfs로 solve한 코드

   import sys
   

sys.setrecursionlimit(10**7)
sys.stdin = open("input.txt")

dx = [1,-1,0,0]
dy = [0,0,1,-1]
def dfs(x,y):
if x == 0 and y == 0:
return 1
if visit[x][y] == -1:
visit[x][y] = 0
for i in range(4):
nx = x + dx[i]
ny = y + dy[i]
if 0<=nx<n and 0<=ny<m:
if matrix[nx][ny] > matrix[x][y]:
visit[x][y] += dfs(nx,ny)
return visit[x][y]

n,m = [int(x) for x in sys.stdin.readline().split()]
matrix = list()
for _ in range(n):
matrix.append([int(x) for x in sys.stdin.readline().split()])
visit = [[-1] * m for _ in range(n)]

print(dfs(n-1,m-1))

2. dfs로 시간초과 코드
dfs와 dp를 함께 이용해야하기에 dfs와 visit배열의 방문 여부를 통해 모두 탐색하면, 시간 초과가 발생한다..

```python3
import sys

sys.setrecursionlimit(10**7)
sys.stdin = open("input.txt")

dx = [1,-1,0,0]
dy = [0,0,1,-1]
answer = 0
def dfs(x,y):
    global answer
    if x == 0 and y == 0:
        answer += 1
    else:
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0<=nx<n and 0<=ny<m and visit[nx][ny] == 0:
                if matrix[nx][ny] > matrix[x][y]:
                    visit[nx][ny] = 1
                    dfs(nx,ny)
                    visit[nx][ny] = 0



n,m = [int(x) for x in sys.stdin.readline().split()]
matrix = list()
for _ in range(n):
    matrix.append([int(x) for x in sys.stdin.readline().split()])
visit = [[0] * m for _ in range(n)]
visit[n-1][m-1] = 1

dfs(n-1,m-1)
print(answer)