[백준/Python]1890_점프

문제

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

1890번: 점프

풀이

처음에 BFS로 풀 때는 메모리 초과가 나오고 DFS로 풀 때는 시간 초과가 나왔습니다.

BFS 코드:

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
matrix = []
answer = 0
for _ in range(n):
    matrix.append(list(map(int, sys.stdin.readline().rstrip().split())))

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

q = deque([(0, 0, matrix[0][0])])
while q:
    y, x, jump = q.popleft()
    if y == n - 1 and x == n - 1:
        answer += 1
        continue
    for i in range(2):
        yy, xx = y + jump * dy[i], x + jump * dx[i]
        if 0 <= yy < n and 0 <= xx < n:
            q.append((yy, xx, matrix[yy][xx]))
print(answer)

DFS 코드:

import sys
from collections import deque


def dfs(ny, nx, jmp):
    global answer
    if ny == n - 1 and nx == n - 1:
        answer += 1
        return
    for i in range(2):
        yy, xx = ny + jmp * dy[i], nx + jmp * dx[i]
        if 0 <= yy < n and 0 <= xx < n:
            dfs(yy, xx, matrix[yy][xx])


n = int(sys.stdin.readline().rstrip())
matrix = []
answer = 0
for _ in range(n):
    matrix.append(list(map(int, sys.stdin.readline().rstrip().split())))

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

dfs(0, 0, matrix[0][0])
print(answer)

결국 dp로 문제를 해결했습니다.

시간 복잡도는 모든 위치를 방문하고 그 위치에서 오른쪽, 아래의 카운트를 각각 dp[y][x] 만큼 올려주기 때문에 (n^2) * 2 = n^2입니다.

코드

import sys

n = int(sys.stdin.readline().rstrip())
matrix = []
for _ in range(n):
    matrix.append(list(map(int, sys.stdin.readline().rstrip().split())))
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1
for y in range(n):
    for x in range(n):
        if matrix[y][x] == 0:
            break
        yy = y + matrix[y][x]
        xx = x + matrix[y][x]
        if 0 <= yy < n:
            dp[yy][x] += dp[y][x]
        if 0 <= xx < n:
            dp[y][xx] += dp[y][x]
print(dp[n - 1][n - 1])