[BOJ] 1520 - 내리막길

김우경·2021년 1월 9일

알고리즘

목록 보기

44/69

문제 링크

문제 설명

N*M 크기의 지도 각 칸에는 해당 지점의 높이가 적혀있다. (0,0)부터 (N-1, M-1)로 이동하려하는데 상하좌우로 이동이 가능하고, 항상 현재 칸보다 높이가 낮은 지점으로만 이동이 가능하다. 가능한 이동경로의 개수는?

문제 풀이

점화식은 쉽게 생각했는데 구현이 어려웠다,,,
1. 상태 정의

$DP[i][j]$ : (0,0)에서 [i][j]로 갈 수 있는 이동경로의 개수
$DP[i][j]$ = 상하좌우 네 방향 중 더 큰 높이를 가진 칸의 dp[x][y] 합

시도 1 - 그냥 dfs

import sys

input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

N, M = map(int, input().split())
board = []
answer = 0
visited = [[0]*M for _ in range(N)]

for _ in range(N):
    board.append(list(map(int, input().split())))
dp = [[1]*M for _ in range(N)]

def in_range(x, y):
    if x in range(N) and y in range(M):
        return True
    return False

def dfs(x, y):
    global answer
    if x == N-1 and y == M-1:
        answer += 1
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if in_range(nx, ny) and board[nx][ny] < board[x][y] and not visited[nx][ny]:
            visited[nx][ny] = 1
            dfs(nx, ny)
            visited[nx][ny] = 0

dfs(0,0)
print(answer)

시간 초과가 난다.

시도 2 - 재귀를 이용한 dp

import sys
from collections import deque

sys.setrecursionlimit(10000)
input = sys.stdin.readline
dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

N, M = map(int, input().split())
board = []
for _ in range(N):
    board.append(list(map(int, input().split())))

def in_range(x, y):
    if x in range(N) and y in range(M):
        return True
    return False

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

def find(x, y):
    if dp[x][y] != 0:
        return dp[x][y]
    for i in range(4):
        nx, ny = x+dx[i], y+dy[i]
        if in_range(nx, ny) and board[nx][ny] > board[x][y]:
            dp[x][y] += find(nx, ny)
    return dp[x][y]


print(find(N-1, M-1))

이 친구도 모든 경우에 대해 재귀를 돌아서 그런가 시간초과가,,

시도 3 - dfs + dp

-> dfs를 (0,0)부터 탐색이 아닌 dp를 이용해서 (N-1, M-1)부터 (0,0)까지 탐색한다. 모든 칸을 탐색하는 것이 아니고, 이미 방문해서 (0,0)에서 해당 칸 까지 가는 경우의 수를 구한 경우에는 바로 값을 리턴한다.

import sys

sys.setrecursionlimit(10000)
input = sys.stdin.readline

dx = [-1, 1, 0, 0]
dy = [0, 0, -1, 1]

N, M = map(int, input().split())
board = []
dp = [[-1]*M for _ in range(N)]
dp[0][0] = 1

for _ in range(N):
    board.append(list(map(int, input().split())))

def in_range(x, y):
    if x in range(N) and y in range(M):
        return True
    return False

def dfs(x, y):
    if x == 0 and y == 0:
        return dp[x][y]
    #방문하지 않은 칸에 대해서
    if dp[x][y] == -1:
        dp[x][y] = 0
        for i in range(4):
            nx, ny = x+dx[i], y+dy[i]
            if in_range(nx, ny) and board[nx][ny] > board[x][y]:
                dp[x][y] += dfs(nx, ny)
    return dp[x][y]

print(dfs(N-1,M-1))