파이썬 알고리즘 076 | 알리바바와 40인의 도둑

76. 알리바바와 40인의 도둑(Bottom-Up) / (Top-Down)

알리바바는 40인의 도둑으로부터 금화를 훔쳐 도망치고 있습니다.
알리바바는 도망치는 길에 평소에 잘 가지 않던 계곡의 돌다리로 도망가고자 한다.
계곡의 돌다리는 N×N개의 돌들로 구성되어 있다. 각 돌다리들은 높이가 서로 다릅니다.
해당 돌다리를 건널때 돌의 높이 만큼 에너지가 소비됩니다. 이동은 최단거리 이동을 합니다.
즉 현재 지점에서 오른쪽 또는 아래쪽으로만 이동해야 합니다.
NxN의 계곡의 돌다리 격자정보가 주어지면 (1, 1)격자에서 (N, N)까지 가는데 드는 에너지의
최소량을 구하는 프로그램을 작성하세요.
만약 N=3이고, 계곡의 돌다리 격자 정보가 다음과 같다면
3 3 5
2 3 4
6 5 2
(1, 1)좌표에서 (3, 3)좌표까지 가는데 드는 최소 에너지는 3+2+3+4+2=14이다.
▣ 입력설명
첫 번째 줄에는 자연수 N(1<=N<=20)이 주어진다.
두 번째 줄부터 계곡의 N*N 격자의 돌다리 높이(10보다 작은 자연수) 정보가 주어진다.
▣ 출력설명
첫 번째 줄에 (1, 1)출발지에서 (N, N)도착지로 가기 위한 최소 에너지를 출력한다.
▣ 입력예제 1
5
3 7 2 1 9
5 8 3 9 2
5 3 1 2 3
5 4 3 2 1
1 7 5 2 4
▣ 출력예제 1
25

<내 풀이>

=> 내가 만든 코드에서 dy를 출력해보면
[0, 0, 0, 0, 0, 0, 0]

[0, 3, 10, 12, 13, 22, 0]

[0, 8, 16, 15, 22, 24, 0]

[0, 13, 16, 17, 19, 22, 0]

[0, 18, 20, 20, 21, 22, 0]

[0, 19, 26, 25, 23, 26, 0]

[0, 0, 0, 0, 0, 0, 0]

이렇게 출력된다
밑에와 같이 출력돼야 하는데 17부분에서 잘못된 판단을 내림 (굵은표시부분)
(15를 선택해서 자기자신(1)을 더해야하는데 16을 선택함 WHY?)

[3, 10, 12, 13, 22]

[8, 16, 15, 22, 24]

[13, 16, 16, 18, 21]

[18, 20, 19, 20, 21]

[19, 26, 24, 22, 25]

어떤 부분이 잘못됐는지 잘 모르겠음

• 나는 a[i][j]로 올 수 있는 방향이 위쪽에서 오는애랑 왼쪽에서 오는애 밖에 없으니깐 걔네 둘중에서 더 작은 값을 dy[i][j]에 a[i][j]랑 같이 넣어주려던 것이 목표였음, 근데 이 예제입력값애서도 그렇고 다른 예제값에서도 자꾸 사소하게 과다해짐
  ==> if a[i-1][j]>=a[i][j-1]
  여기서 이거 비교하는 게아니라 dy, 지금까지 축적된 경로의 경우의 수 를 비교했어야 한다..

n=int(input())
dy=[[0]*(n+2) for _ in range(n+2)]
a=[list(map(int,input().split())) for _ in range(n)]
a.insert(0,[0]*(n+1))
a.append([0]*(n+1))
for i in range(1,n+1):
    a[i].insert(0,0)
    a[i].append(0)
dy[1][1]=a[1][1]
for i in range(1,n+1):
    for j in range(1,n+1) :
        if a[i-1][j]>=a[i][j-1] and a[i][j-1]>0: #여기서 비교하는 값 틀림
            dy[i][j]=a[i][j]+dy[i][j-1]
        elif a[i-1][j]<a[i][j-1] and a[i-1][j]>0:
            dy[i][j]=a[i][j]+dy[i-1][j]
        elif a[i-1][j]>a[i][j-1] and a[i][j-1]==0:
            dy[i][j]=a[i][j]+dy[i-1][j]
        elif a[i-1][j]<a[i][j-1] and a[i-1][j]==0:  
             dy[i][j]=a[i][j]+dy[i][j-1] 
for i in dy:
    print(i)
    

(2) 최종 풀이

n=int(input())
dy=[[0]*(n+2) for _ in range(n+2)]
a=[list(map(int,input().split())) for _ in range(n)]
a.insert(0,[0]*(n+1))
a.append([0]*(n+1))
for i in range(1,n+1):
    a[i].insert(0,0)
    a[i].append(0)
dy[1][1]=a[1][1]
for i in range(1,n+1):
    for j in range(1,n+1) :
        if dy[i-1][j]>=dy[i][j-1] and a[i][j-1]>0:
            dy[i][j]=a[i][j]+dy[i][j-1]
        elif dy[i-1][j]<dy[i][j-1] and a[i-1][j]>0:
            dy[i][j]=a[i][j]+dy[i-1][j]
        elif dy[i-1][j]>dy[i][j-1] and a[i][j-1]==0:
            dy[i][j]=a[i][j]+dy[i-1][j]
        elif dy[i-1][j]<dy[i][j-1] and a[i-1][j]==0:  
             dy[i][j]=a[i][j]+dy[i][j-1] 
print(dy[n][n])

<풀이>

(1) Bottom-Up 방식

• 가장자리 우선 처리

if __name__=='__main__':
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    dy=[[0]*n for _ in range(n)]
    dy[0][0]=arr[0][0]
    for i in range(n) : #처음엔 가장 자리를 처리해주는 것
        dy[0][i]=dy[0][i-1] + arr[0][i] #자기 왼편 +자신 값
        dy[i][0]=dy[i-1][0] + arr[i][0] 
    for i in range(1, n) : 
        for j in range(1,n) : 
            dy[i][j]=min(dy[i-1][j], dy[i][j-1]) + arr[i][j]
    print(dy[n-1][n-1])

(2) Top - Down dfs 활용 - 메모이제이션 아직 안해서 Time Limit 걸리는 것

def dfs(x,y) :
    if x==0 and y==0:
        return arr[0][0]
    else : 
        if y==0 :
            return dfs(x-1,y)+arr[x][y] #y는 0이니깐 건들지말고 x만 move
        elif x==0:
            return dfs(x,y-1) + arr[x][y]
        else :
            return min(dfs(x-1,y), dfs(x,y-1))+arr[x][y]
if __name__=='__main__':
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    dy=[[0]*n for _ in range(n)]
    print(dfs(n-1,n-1))

(3) Top - Down dfs 활용 - 메모이제이션 한 것

def dfs(x,y) :
    if dy[x][y]>0: #dy[x][y]가 이미 있으면 그냐 넘어가기
        return dy[x][y]
    if x==0 and y==0:
        return arr[0][0]
    else : 
        if y==0 :
            dy[x][y]= dfs(x-1,y)+arr[x][y] 
        elif x==0:
            dy[x][y]= dfs(x,y-1) + arr[x][y]
        else :
            dy[x][y]= min(dfs(x-1,y), dfs(x,y-1))+arr[x][y]
        return dy[x][y] #dy[x][y]를 어찌됐건 출력해준다
if __name__=='__main__':
    n=int(input())
    arr=[list(map(int,input().split())) for _ in range(n)]
    dy=[[0]*n for _ in range(n)]
    print(dfs(n-1,n-1))

<반성점>

• 강사님과 접근한 방식은 똑같았는데
  비교값을 착각한 점이 아쉽다 동적 부분은 dy를 비교하는 게 핵심이다 그동안 축적되어온 것들..
• 그냥 굳이 0으로 안 둘러주고, 가장 자리 부분들만 따로 처리해주는 것도 가능했을 것이다

<배운 점>

• 가장자리 먼저 처리해주는 방법 있음

<2차 내 풀이>

n=int(input())
a=[list(map(int,input().split())) for _ in range(n)]
dy=[[0]*(n+1) for _ in range(n)]
dy[0][0]=a[0][0]

for i in range(n) :
    for j in range(n) :
        if i-1<0 :
            dy[i][j]=dy[i][j-1]+a[i][j]
        elif j-1<0:
            dy[i][j]=dy[i-1][j]+a[i][j]
        else:
            dy[i][j]=min(dy[i][j-1],dy[i-1][j]) + a[i][j]

print(dy[n-1][n-1])