[BOJ/Python] 백준 11048번 - 이동하기

백준 #11048 이동하기

11048번: 이동하기

import sys
input = sys.stdin.readline

def in_range(r, c):
  return 0 <= r < n and 0 <= c < m
  
n, m = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]
dp = [[0 for _ in range(m)] for _ in range(n)]
for i in range(n):
  for j in range(m):
    if i == 0 and j == 0:
      dp[i][j] = maze[i][j]
    else:
      if in_range(i-1, j):
        dp[i][j] = max(dp[i-1][j] +  maze[i][j], dp[i][j])
      if in_range(i, j-1):
        dp[i][j] = max(dp[i][j-1] +  maze[i][j], dp[i][j])
      if in_range(i-1, j-1):
        dp[i][j] = max(dp[i-1][j-1] +  maze[i][j], dp[i][j])
      
print(dp[n-1][m-1])

BFS로 풀었다가 시간 초과, 메모리 초과가 나서 DP로 다시 풀었다. (0, 0)부터 시작해서 (n, m)까지 모든 공간을 방문하면서 해당 공간에 도착했을 때 최대 캔디 수를 DP 리스트에 저장한다. 초깃값은 시작 위치인 (0, 0)의 캔디수가 된다. 최대 캔디 수는 미로의 크기를 벗어나지 않는 한에서 (i-1, j) 또는 (i, j-1) 또는 (i-1, j-1)에서 (i, j)로 이동했을 때 얻을 수 있는 캔디의 수 중 가장 큰 값이 저장된다.

 

BFS로 푼 코드도 첨부한다.

from collections import deque
import sys
input = sys.stdin.readline

def in_range(r, c):
  return 0 <= r < n and 0 <= c < m

def bfs():
  q = deque()
  q.append((0, 0))
  while q:
    i, j = q.popleft()
    for r, c in (i+1, j), (i, j+1), (i+1, j+1):
      if in_range(r, c) and visited[r][c] == 0:
        visited[r][c] = visited[i][j] + maze[r][c]
        q.append((r, c))
      elif in_range(r, c) and visited[r][c] != 0:
        visited[r][c] = max(visited[r][c], visited[i][j] + maze[r][c])

n, m = map(int, input().split())
maze = [list(map(int, input().split())) for _ in range(n)]
visited = [[0 for _ in range(m)] for _ in range(n)]
visited[0][0] = maze[0][0]
bfs()
print(visited[n-1][m-1])