[파이썬] 백준 - 내리막 길

내리막 길 성공출처

시간 제한메모리 제한제출정답맞은 사람정답 비율

2 초

128 MB

43375

11787

8431

28.321%

 

출처
Olympiad > 한국정보올림피아드 > 한국정보올림피아드시․도지역본선 > 지역본선 2006 > 고등부 3번
데이터를 추가한 사람: cgiosy, doju, kch616
문제의 오타를 찾은 사람: imgosari
잘못된 데이터를 찾은 사람: mygumi, tncks0121

 

알고리즘 분류
다이나믹 프로그래밍
그래프 이론
그래프 탐색
깊이 우선 탐색

 

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

1520번: 내리막 길

---

import collections, sys
sys.setrecursionlimit(100000)

x_move = [1, 0, -1, 0]
y_move = [0, 1, 0, -1]

M, N = map(int, input().split())
board = []
dp = [[-1 for y in range(N)] for x in range(M)]
for i in range(M):
    board.append(list(map(int, input().split())))

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

    dp[x][y] = 0
    for i in range(4):
        new_x = x + x_move[i]
        new_y = y + y_move[i]

        if 0<=new_x<M and 0<=new_y<N and board[x][y] > board[new_x][new_y]:
            dp[x][y] += dfs(new_x,new_y)

    return dp[x][y]

print(dfs(0,0))

 

후기

 DFS + DP 문제다. 

 알고리즘 분류를 못봤으면 그냥 DFS로 풀었을 문제였다. DFS로 풀면 시간초과가 난다고 한다.

 그리고 파이썬의 경우, 이 문제는  sys를 import해주고 setrecursionlimit( )을 사용해서 재귀 횟수를 늘려줘야한다. 이것 때문에 꽤 애먹는데 다른 풀이를 보고 고쳤다.

 

풀이

 시작점에서 DFS를 시작한다.(반대로 도착점에서 DFS를 시작해도 된다.)

 board는 문제에서 지도를 뜻하고, dp[x][y] 는 x행y열에서 도착지까지의 경로가 몇 개 있는지 뜻한다.

 dp는 맨 처음에 전부 -1로 초기화한다. 그리고 dfs 안에서 시작할 때 dp[][] = 0으로 만든다.

 dp를 맨 처음에 0으로 초기화 하지 않는 이유는, dp[][] 값이 0이 될 수도 있기 때문이다.

 예를 들어, dp를 0으로 초기화 했을 경우 아래와 같은 지도일 때는

시작(1)	(2)
(2)	(2)

 시작점 dp 값은 0이 된다. 하지만 경로가 막혀서 0인건지 방문을 하지 않아서 0인건지를 모른다...

 때문에 가장 dp는 -1로 초기화를 하고, 일단 방문했다는 표시로 dp[x][y]를 0으로 넣는다.

 

 dp값이 이미 존재할 경우( != -1 ) dfs를 돌지 않고 해당 dp값을 리턴해준다. 이 과정을 통해서 시간복잡도가 상당히 줄어드는 것이고 DFS+DP를 사용하는 이유인듯하다.

 그리고 dfs를 돌며 목적지까지 도달했으면 1을 리턴.

 이후 4방향을 돌며 새로운 쪽으로 DFS를 돌고 리턴 값을 더해주면 시작점에 경로의 총합이 나온다.