[baekjoon] 백준 1890번(파이썬): 점프

문제

1890번: 점프

알고리즘

- 반복문을 통해 갈 수 있는 그래프의 좌표를 탐색한다

- 현재 탐색하는 좌표가 오른쪽 아래 맨 끝 점이면 반복을 멈추고 오른쪽 아래 맨 끝 점까지 이동 가능한 개수를 출력한다.

- 오른쪽과 아래로 이동할 수 있다면 이동하고 그전 좌표까지 이동 가능한 값을 더한다.

코드

import sys

n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
dp = [[0] * n for _ in range(n)]
dp[0][0] = 1 # 초기 값

# 반복문을 통해 갈 수 있는 그래프의 좌표를 탐색
for i in range(n):
    for j in range(n):

        # 현재 탐색하는 좌표가 오른쪽 맨 끝 점이면 반복을 멈춘다.
        if i == n - 1 and j == n - 1:
            print(dp[i][j])
            break

        # 오른쪽으로 이동
        if j + graph[i][j] < n:
            dp[i][j + graph[i][j]] += dp[i][j]

        # 아래로 이동
        if i + graph[i][j] < n:
            dp[i + graph[i][j]][j] += dp[i][j]

 

 

실패한 코드(메모리 초과..)

import sys
from collections import deque


def bfs():
    queue = deque([[0, 0]])
    while queue:
        x, y = queue.popleft()
        if x == n - 1 and y == n - 1:
            continue

        dx = [graph[x][y], 0]
        dy = [0, graph[x][y]]

        for i in range(2):
            nx = x + dx[i]
            ny = y + dy[i]
            if 0 <= nx < n and 0 <= ny < n:
                queue.append([nx, ny])
                visited[nx][ny] += 1


n = int(sys.stdin.readline())
graph = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
visited = [[0] * n for _ in range(n)]
bfs()
print(visited[n - 1][n - 1])

bfs를 통해 문제를 수행했지만 메모리 초과가 나왔다.
queue에 이미 갔던 곳을 계속해서 추가했기 때문에 메모리 초과가 나온 것으로 판단이 된다.

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법