[백준 문제풀이] 얼렁뚱땅 11048 이동하기 풀이

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

 

11048번: 이동하기

노트북을 맥북으로 바꿨는데, 화면크기 키우는건 알겠는데 줄이는건 몰라서

이제는 캡처하지 않고 그냥 링크만 올리겠습니다 ^^ ..

 

맥북사서 기분낼려고 스벅왔는데 시끄러운걸 걱정했던 것은 노이즈캔슬링으로 인해 OK 괜춘

하지만, 코로나 이후 만성 콧물 및 코막힘에 시달리는 민지에게 에어컨 바람은 콧물을 유발하네요 ㅎㅎ

집 가겠슴다 그럼 뿅

 

bfs : 시간 초과

from collections import deque

n, m = map(int,input().split())
array = [list(map(int,input().split())) for _ in range(n)]
visited = [[-1]*m for i in range(n)]

q = deque()
q.append([0,0,array[0][0]])

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

while q :
    x,y,temp_sum = q.popleft()

    if visited[x][y] > temp_sum :
        continue
    
    for i in range(len(dx)) :
        nx = x + dx[i]
        ny = y + dy[i]
        if 0<=nx<n and 0<=ny<m :
            real_temp = temp_sum + array[nx][ny]
            if visited[nx][ny] < real_temp :
                visited[nx][ny] = real_temp
                q.append([nx,ny,real_temp])

print(visited[n-1][m-1])

 

dp : 통과 !! 지섭쿤 감사요

n, m = map(int,input().split())
array = [list(map(int,input().split())) for _ in range(n)]
visited = [[-1]*m for i in range(n)]
visited[0][0] = array[0][0]

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


for i in range(n) :
    for j in range(m) :
        for k in range(len(dx)) :
            nx = i + dx[k]
            ny = j + dy[k]
            if 0<=nx<n and 0<=ny<m :
                visited[nx][ny] = max(visited[nx][ny], visited[i][j] + array[nx][ny])

print(visited[n-1][m-1])