[백준] 1520번 : 내리막 길 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

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

 

1. 문제 설명

반응형

2. 풀이과정

해당 문제는 이전 위치에서 다음 위치로 이동할 때 다음 위치가 이전 위치보다 낮은 높이로 이동해야 한다.

마지막 위치까지 이동하면서 이동 가능한 총 이동 가능 경로의 수를 반환하는 문제이다.

지도를 이동하는 문제라는 점에서 dfs나 bfs 알고리즘으로 해결해야 한다는 것을 파악할 수 있다.

또 이동 가능한 총 경로의 수를 반환해야 한다는 점에서 이전의 결과들을 저장하는 다이나믹 프로그래밍 알고리즘을 활용해야 한다는 것도 파악할 수 있다.

dfs 알고리즘으로 0, 0에서 출발하여 이동 가능한 다음 위치를 찾아 최대한 마지막 위치까지 이동한다.

만약 마지막 위치에 도달하면 가능한 경로를 찾았으므로 1을 반환한다. 

만약 도달한 위치가 이전 경로를 찾을 때 지나갔던 위치이면, 해당 위치에 저장된 가능한 경로의 수를 반환하여 해당 위치에서부터 가능한 경로를 반환해 준다.

두 경우가 아니라면 이동 가능한 다음 위치를 찾아 이동하며 가능한 경로의 수를 더한다.

마지막 위치에서부터 처음 위치까지 올라오며 계속적으로 현재 위치에 이동 가능한 경로의 수를 저장한다.

마지막에 시작 위치의 0, 0의 값을 반환하면 총 이동 가능한 경로의 수를 구할 수 있다.

 

※ 수정 : 통과했던 문제가 데이터 추가로 인해 재귀초과가 발생하였다.

재귀 문제를 풀 때는  sys.setrecursionlimit(10 ** 6)를 꼭 작성해 주도록 해야겠다.

1. sys.stdin.readline() 함수를 사용하기 위해 sys 모듈을 불러온다. import sys
2. 데이터가 추가되면서 통과가 재귀초과 실패로 바뀌었다. 재귀 문제를 푼다면 꼭 상단에 적어주는 것을 잊지 말아야겠다. sys.setrecursionlimit(10 ** 6)
3. 지도의 세로 크기와 가로 크기를 입력받는다. M, N = map(int, sys.stdin.readline().split())
4. 지도의 정보를 저장할 리스트를 생성한다. MAP = []
5. 지도의 각 행을 입력받아 리스트로 만들어 지도의 정보 리스트에 추가한다. for _ in range(M): MAP.append(list(map(int, sys.stdin.readline().split())))
6. dfs 알고리즘으로 지도를 탐색하기 위한 함수를 생성한다. def dfs(now_X, now_Y)
   1. 만약 현재 위치가 마지막 위치이면 1을 반환한다. if (now_X == M - 1) and (now_Y == N - 1): return 1
   2. 만약 현재 위치가 이전에 한 번이라도 방문했던 위치이면 해당 위치에 저장되어 있는 값을 반환한다. if (dp[now_X][now_Y] != -1): return dp[now_X][now_Y]
   3. 이동 가능한 경로의 수를 저장할 변수를 생성하고 초기화한다. cases = 0
   4. 상하좌우 움직일 수 있는 방향으로 움직이며 for m in move
      1. 다음 위치를 저장한다. next_X = now_X + m[0]
      2. next_Y = now_Y + m[1]
      3. 만약 다음 위치가 지도에서 이동 가능한 위치이고 이전 위치보다 낮은 높이라면 이동 가능한 경로 수에 해당 위치에서부터 지도를 탐색한 결과를 더해준다. if (0 <= next_X < M) and (0 <= next_Y < N) and (MAP[now_X][now_Y] > MAP[next_X][next_Y]): cases += dfs(next_X, next_Y)
   5. 현재 위치에 가능한 경로의 수를 저장한다. dp[now_X][now_Y] = cases
   6. 현재 위치에 저장된 가능한 경로의 수를 반환한다. return dp[now_X][now_Y]
7. 움직일 수 있는 상하좌우, 4방향의 좌표 움직임을 2차원 리스트로 저장한다. move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
8. 가능한 경로의 수를 저장할 2차원 배열을 지도의 크기와 동일하게 생성하고 모두 -1 저장한다. dp = [ [-1] * N for _ in range(M) ]
9. 시작 위치인 0, 0부터 탐색을 시작하여 그 결과를 반환하고 출력한다. print(dfs(0, 0))

3. 소스코드

import sys
sys.setrecursionlimit(10 ** 6)

M, N = map(int, sys.stdin.readline().split())

MAP = []
for _ in range(M):
    MAP.append(list(map(int, sys.stdin.readline().split())))

def dfs(now_X, now_Y):
    if (now_X == M - 1) and (now_Y == N - 1):
        return 1
    
    if (dp[now_X][now_Y] != -1):
        return dp[now_X][now_Y]

    cases = 0
    for m in move:
        next_X = now_X + m[0]
        next_Y = now_Y + m[1]
        if (0 <= next_X < M) and (0 <= next_Y < N) and (MAP[now_X][now_Y] > MAP[next_X][next_Y]):
            cases += dfs(next_X, next_Y)

    dp[now_X][now_Y] = cases
    return dp[now_X][now_Y]


move = [[-1, 0], [1, 0], [0, -1], [0, 1]]
dp = [ [-1] * N for _ in range(M) ]

print(dfs(0, 0))