파이썬 알고리즘 287번 | [백준 11909번] 배열 탈출 - DP, 다익스트라

287. 배열탈출

1) 어떤 전략(알고리즘)으로 해결?

다이나믹 프로그래밍
그래프 이론
데이크스트라

2) 코딩 설명

<내 풀이>

import sys

n = int(sys.stdin.readline()) 
graph =[[0 for _ in range(n+1)]]
cost_save = [ [0 for _ in range(n+1)] for _ in range(n+1) ]

for i in range(n) :
    add=[0]+(list(map(int,sys.stdin.readline().split())))
    graph.append(add)

# 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
# i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
# 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
# i=j=n인 경우 바로 출구 (nn)
# A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]
# 버튼을 한 번 누르는 데에는 1원의 비용

for i in range(1,n+1) : # 왼쪽이랑 위만 검사하면 됨 
    for j in range(1,n+1) : 
        cost_up = int(1e9)
        cost_left = int(1e9)

        if i-1<1 and j-1<1 : #왼쪽이나 위가 존재하지 않음 
            continue 

        # 위 가능하면 
        if i-1>=1 :
            cost_up = cost_save[i-1][j]
            # 위의 아이(graph[i-1][j])가 나(graph[i][j])보다 커야지 그냥 내려옴
            # 내가 더 크다면 위의 아이를 나보다 크게 만들어줄 비용 발생 
            if graph[i][j] >= graph[i-1][j] : 
                cost_up+=(graph[i][j]-graph[i-1][j])+1
                
        # 왼쪽 가능하면 
        if j-1>=1 :
            cost_left = cost_save[i][j-1]
            if graph[i][j] >= graph[i][j-1] : 
                cost_left+=(graph[i][j]-graph[i][j-1])+1
                
        # 둘 중 더 작은 애를 내 비용으로 
        cost_save[i][j] = min(cost_up, cost_left)

print(cost_save[n][n])

< 내 틀렸던 풀이, 문제점>

<다익스트라 접근>

(1) bfs 로 접근하려고 했는데 메모리 초과

• 큐에 너무 많이 넣어서 그런 것으로 추정

from collections import deque
import sys

n = int(sys.stdin.readline()) 
graph =[[0 for _ in range(n)]]
q=deque()
cost = int(1e9)
for i in range(n) :
    add=[0]+(list(map(int,sys.stdin.readline().split())))
    graph.append(add)

# 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
# i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
# 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
# i=j=n인 경우 바로 출구 (nn)

#  A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]
# 버튼을 한 번 누르는 데에는 1원의 비용

q.append((1,1,0))

while q :
    plus=0
    nowr, nowc, now_cost = q.popleft()
    #print(nowr,nowc,now_cost, q)
    if nowr==n and nowc==n :
        #print(now_cost, " now cost\n")
        if now_cost<cost:
            cost=now_cost
            #break
            
    elif 1<=nowr and nowc < n :
        while graph[nowr][nowc] <= graph[nowr][nowc+1] :
                graph[nowr][nowc]+=1
                plus+=1
        graph[nowr][nowc]-=plus
        q.append((nowr, nowc+1, now_cost+plus))

        plus=0
        if nowr<=n-1 : 
            while graph[nowr][nowc] <= graph[nowr+1][nowc] :
                graph[nowr][nowc]+=1
                plus+=1
            graph[nowr][nowc]-=plus
            q.append((nowr+1, nowc, now_cost+plus))
        
    elif 1==nowr and 1<=nowc<n :
        while graph[nowr][nowc] <= graph[nowr][nowc+1] :
            graph[nowr][nowc]+=1
            plus+=1
        graph[nowr][nowc]-=plus
        q.append((nowr, nowc+1, now_cost+plus))
    
    elif 1<=nowr<n and nowc==n :
        while graph[nowr][nowc] <= graph[nowr+1][nowc] :
            graph[nowr][nowc]+=1
            plus+=1
        graph[nowr][nowc]-=plus
        q.append((nowr+1, nowc, now_cost+plus))

print(cost)

(2) heap (min) 으로 구현 & while 문 제거했는데도 여전히 시간초과

from collections import deque
import heapq
import sys

n = int(sys.stdin.readline()) 
graph =[[0 for _ in range(n)]]
hq=[]

cost = int(1e9)
cost_save = [ [int(1e9) for _ in range(n+1)] for _ in range(n+1) ]
for i in range(n) :
    add=[0]+(list(map(int,sys.stdin.readline().split())))
    graph.append(add)

# 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
# i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
# 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
# i=j=n인 경우 바로 출구 (nn)
# A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]
# 버튼을 한 번 누르는 데에는 1원의 비용

hq.append((0,1,1)) # 비용

while hq :
    plus=0
    now_cost, nowr, nowc = heapq.heappop(hq)
    # print(nowr,nowc,now_cost, hq)
    if nowr==n and nowc==n :
        if now_cost<cost:
            cost=now_cost

    if cost_save[nowr][nowc] < now_cost:
        continue
            
    elif 1<=nowr and nowc < n :
        if cost_save[nowr][nowc+1]>=now_cost: # add
            if graph[nowr][nowc] <= graph[nowr][nowc+1] :
                    plus = graph[nowr][nowc+1]-graph[nowr][nowc]+1
            cost_save[nowr][nowc+1] = now_cost+plus
            heapq.heappush(hq,(now_cost+plus,nowr, nowc+1))

        if nowr<=n-1 : 
            if cost_save[nowr+1][nowc]>=now_cost: # add
                if graph[nowr][nowc] <= graph[nowr+1][nowc] :
                    plus = graph[nowr+1][nowc]-graph[nowr][nowc]+1
                cost_save[nowr+1][nowc] = now_cost+plus
                heapq.heappush(hq,(now_cost+plus,nowr+1, nowc ))
        
    elif 1==nowr and 1<=nowc<n :
        if cost_save[nowr][nowc+1]>=now_cost: # add
            if graph[nowr][nowc] <= graph[nowr][nowc+1] :
                plus = graph[nowr][nowc+1]-graph[nowr][nowc]+1
            cost_save[nowr][nowc+1] = now_cost+plus
            heapq.heappush(hq,(now_cost+plus, nowr, nowc+1 ))
    
    elif 1<=nowr<n and nowc==n :
        if cost_save[nowr+1][nowc]>=now_cost: # add
            if graph[nowr][nowc] <= graph[nowr+1][nowc] :
                plus = graph[nowr+1][nowc] - graph[nowr][nowc]+1
            cost_save[nowr+1][nowc] = now_cost+plus
            heapq.heappush(hq,(now_cost+plus, nowr+1, nowc ))

print(cost)

(3) 코드 간소화 - 여전히 시간초과 !

import heapq
import sys

n = int(sys.stdin.readline()) 
graph =[[0 for _ in range(n)]]
hq=[] # min heap
disr = [1, 0] # 오른쪽 
disc = [0, 1] # 아래
cost_save = [ [int(1e9) for _ in range(n+1)] for _ in range(n+1) ]

for i in range(n) :
    add=[0]+(list(map(int,sys.stdin.readline().split())))
    graph.append(add)

# 1≤i,j<n이라면, 상수는 A[i][j+1] 또는 A[i+1][j]로만 건너갑니다.
# i=n,1≤j<n이라면, A[i][j+1]로만 건너갑니다.
# 1≤i<n,j=n이라면 A[i+1][j]로만 건너갑니다.
# i=j=n인 경우 바로 출구 (nn)
# A[a][b]에서 A[c][d]로 건너가려면 A[a][b]>A[c][d]
# 버튼을 한 번 누르는 데에는 1원의 비용

hq.append((0,1,1)) # 비용

while hq :
    now_cost, nowr, nowc = heapq.heappop(hq)
    if cost_save[nowr][nowc] < now_cost:
        continue
    for i in range(2) :
        if 1<=nowr+disr[i]<n+1 and 1<=nowc+disc[i]<n+1 : 
            plus=0
            tmpr = nowr+disr[i]
            tmpc = nowc+disc[i]
            if cost_save[tmpr][tmpc]>=now_cost: # add
                if graph[nowr][nowc] <= graph[tmpr][tmpc] :
                        plus = graph[tmpr][tmpc]-graph[nowr][nowc]+1
                cost_save[tmpr][tmpc] = now_cost+plus
                heapq.heappush(hq,(now_cost+plus,tmpr, tmpc))

print(cost_save[n][n])

다익스트라는 시간초과 나는 것으로 추정 ,,, 적어도 파이썬에서는 ?
=> DP 로 풀어야겠다 ,,

REFERENCE

https://konghana01.tistory.com/342?category=961125

<반성 점>

시간 복잡도가 빡센 것 같으면 dp