[DP] [DFS] 백준 1520 내리막길 +a
문제 출처; https://www.acmicpc.net/problem/1520
1520번: 내리막 길
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다. 현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지
www.acmicpc.net
위의 그림에서 왼쪽 끝에서부터 오른쪽 아래까지 지나갈 수 있는 경로 수에 대해서 구해야 한다. 단, 움직일 때 원래 위치한 곳의 숫자가 이동하는 곳의 숫자보다 커야 한다. input data는 python의 경우 lists of list로 표현된다. input data를 list of list로 만들어서 route라는 변수에 저장하였다. 이때, a, b는 각각 route의 높이의 길이, 너비의 길이를 나타낸다. 한편으로, c라는 변수에는 각각의 위치를 방문했는지를 나타내는 정보를 저장하는 동시에(과거에 방문하지 않았을 경우 -1값을 가지게 된다.) 현 위치에서 이동가능한 오른쪽, 왼쪽, 위, 아래의 위치에 적힌 숫자들을 비교하여 현재 위치에서 출발하였을 때 최종적인 위치까지 갈 수 있는 경우의 수를 담게 된다. 현 위치에서 이동 가능한 위치들과의 숫자들을 비교하기 위해서 move_x, move_y 리스트를 만들었다. move_x, move_y의 경우 x의 숫자에 1과 y의 숫자에 0을 더하게 되므로, 현재 위치에서 아래로 이동하는 위치와의 비교를 가능케 한다. move_x의 인덱스 0 값에 1이 담기므로, 너비탐색 위주가 아니라 깊이 탐색을 위한 것임을 알 수 있다.
풀이한 코드는 다음과 같다.
a, b = len(route), len(route[0])
c = [[-1]*b for i in range(a)]
move_x = [1, -1, 0, 0]
move_y = [0, 0, 1, -1]
def dfs(x,y):
if x == a-1 and y == b-1:
return 1
if c[x][y] != -1:
return c[x][y]
c[x][y] = 0
for i in range(4):
new_x = x + move_x[i]
new_y = y + move_y[i]
if 0 <=new_x<a and 0<= new_y<b:
if route[new_x][new_y] < route[x][y]:
c[x][y] += dfs(new_x, new_y)
return c[x][y]
이 문제를 풀면서 모 기업에서 풀었던 문제와 상당히 유사하다는 걸 느꼈다. 다음의 링크 건 문제와 비슷하였는데, 그게 파이프를 제거하여라였는지 파이프를 통해서 가능한 경로의 수였는지는 정확하게 기억은 안 난다.