| 시간 제한 | 메모리 제한 |
| 2초 | 128MB |
문제
여행을 떠난 세준이는 지도를 하나 구하였다. 이 지도는 아래 그림(생략)과 같이 직사각형 모양이며 여러 칸으로 나뉘어져 있다. 한 칸은 한 지점을 나타내는데 각 칸에는 그 지점의 높이가 쓰여 있으며, 각 지점 사이의 이동은 지도에서 상하좌우 이웃한 곳끼리만 가능하다.
현재 제일 왼쪽 위 칸이 나타내는 지점에 있는 세준이는 제일 오른쪽 아래 칸이 나타내는 지점으로 가려고 한다. 그런데 가능한 힘을 적게 들이고 싶어 항상 높이가 더 낮은 지점으로만 이동하여 목표 지점까지 가고자 한다. 위와 같은 지도에서는 다음과 같은 세 가지 경로(생략)가 가능하다.
지도가 주어질 때 이와 같이 제일 왼쪽 위 지점에서 출발하여 제일 오른쪽 아래 지점까지 항상 내리막길로만 이동하는 경로의 개수를 구하는 프로그램을 작성하시오.
입력
첫째 줄에는 지도의 세로의 크기 M과 가로의 크기 N이 빈칸을 사이에 두고 주어진다. 이어 다음 M개 줄에 걸쳐 한 줄에 N개씩 위에서부터 차례로 각 지점의 높이가 빈 칸을 사이에 두고 주어진다. M과 N은 각각 500이하의 자연수이고, 각 지점의 높이는 10000이하의 자연수이다.
출력
첫째 줄에 이동 가능한 경로의 수 H를 출력한다. 모든 입력에 대하여 H는 10억 이하의 음이 아닌 정수이다.
풀이
1. DFS(시간초과)
M, N = map(int, input().split())
board = []
check = [[False for j in range(N)] for i in range(M)]
d = [[-1,0],[0,1],[1,0],[0,-1]]
for i in range(M):
board.append(list(map(int, input().split())))
count = 0
def dfs(x, y):
check[x][y] = True
if x == M - 1 and y == N - 1:
global count
count += 1
return
for i in range(4):
dx = x + d[i][0]
dy = y + d[i][1]
if dx < 0 or dy < 0 or dx >= M or dy >= N:
continue
if check[dx][dy]:
continue
if board[x][y] > board[dx][dy]:
dfs(dx, dy)
check[dx][dy] = False
dfs(0,0)
print(count)최대 500*500 크기의 배열이고 최단거리도 아닌 경로 탐색이라 너무 가능한 경우가 많아 당연히 시간초과가 뜨리라 예상했다. (왜 짰니 그럼...)
2. DP+DFS
dfs로 수행하는 탐색의 가장 큰 문제는 이전 데이터를 활용하지 못한다는 점이다. 만약 (x, y) 좌표의 지점에서 (x + 1, y)로 이동이 가능하다면 (x, y)에 도착하는 경우의 수를 그대로 (x + 1, y)에 도착하는 경우의 수에 더해주면 된다. 이렇게 특정 좌표로 올 수 있는 인접한 좌표까지의 경우의 수를 모두 더해 새로운 경우의 수를 만들어내면 된다. 여기서 문제는 (x, y)까지 도착하는 경우의 수 역시 같은 방법으로 완성되어있어야 한다는 것이다. 여기서 dp와 dfs를 섞어야 한다.
깊이우선탐색을 하되, 이미 탐색한 곳이라면 저장된 값을 그대로 반환해 불필요한 탐색을 줄인다. 탐색은 (0, 0)부터 시작해 이곳에서 갈 수 있는 모든 지점의 값을 dfs로 재귀호출해 반환 값을 누적해 저장한다. 호출된 함수에서는 다시 인접한 곳에서 불러온다. 원래는 여기서 상위 단계의 지점에 돌아갈 수 없도록 하는 장치가 필요하지만 이 문제에서는 내리막 길만을 이용한다는 조건이 있기 때문에 탐색 실행 조건에 높이 값이 더 적은 곳으로만 탐색을 수행하게 하면 탐색 했던 곳인지 확인할 필요가 없다.
| X \ Y | 0 | 1 | 2 | 3 | 4 |
| 0 | 50 | 45 | 37 | 32 | 30 |
| 1 | 35 | 50 | 40 | 20 | 25 |
| 2 | 30 | 30 | 25 | 17 | 28 |
| 3 | 27 | 24 | 22 | 15 | 10 |
(0, 0)부터 탐색을 시작하면 첫 단계에서 (0, 1), (1, 0)의 값을 호출하게 된다. (0, 1)에서는 (0, 2)을, 다시 (0, 3)을 호출하고 여기서 (0, 4), (1, 3)을 호출하게 된다. 이런식으로 호출을 반복해 (4, 3)을 호출하면 1을 반환한다. (4, 2), (3, 4)는 각각 호출한 (4, 3)에서 1을 받아 누적하게 될 것이다. 반환이 되면서 다른 배열에 그 값을 저장해놓으면 다른 방향에서 같은 값을 호출했을 때 탐색하지 않고 저장된 값을 바로 반환해줄 수 있다. (메모이제이션)
정답 코드
M, N = map(int, input().split())
board = []
dp = [[-1 for j in range(N)] for i in range(M)]
d = [[-1,0],[0,1],[1,0],[0,-1]]
for i in range(M):
board.append(list(map(int, input().split())))
def dfs(x, y):
if x == M - 1 and y == N - 1:
return 1
if dp[x][y] >= 0:
return dp[x][y]
result = 0
for i in range(4):
dx = x + d[i][0]
dy = y + d[i][1]
if 0 <= dx < M and 0 <= dy < N and board[x][y] > board[dx][dy]:
result += dfs(dx, dy)
dp[x][y] = result
return result
print(dfs(0, 0))
