[BOJ|PYTHON]외판원의 순환 DP(top down과 bottom up)

밑은 내가 맨 처음에 호다닥 작성한 코드. 그리고 시간초과를 받았다😥
bottom up 방식으로, 외판원이 현재 위치에서 갈 수 있는 위치로 간 후 갱신 -> 다시 그 위치에서 갈 수 있는 위치로 간 후 갱신 ---> 이 방법을 반복하였다. 어떻게 보면 DFS 느낌?으로 해결하려 했다.(이 발상이 이게 참 문제임 )

이 코드의 문제는 DP에서 가장 중요한 문제인 MEMOIZATION이었다.
DP 테이블을 갱신하는 방법은 이미 계산된 결과 이용하기 가 바탕이고, 다양한 방법이 있는데,
내가 짠 건.. 앞에서 왔던 길을 보는 게 아니라 갈 길에 체크를 하는 ,, 아주 바보같고 느린 방법을 사용했다.

암튼 이 코드는 매우 비효율적. '차곡차곡 쌓자'라는 접근방식을 자꾸 생각하는 걸 줄여나갈 필요가 있다. 배낭문제 구현도 처음 생각해낸 방법이 아래와 같았다..ㅠ 아무래도 그런 풀이법을 떠올리는 게 습관이 된 듯. 방법은 혹독한 연습뿐이겠지..

import sys
input=sys.stdin.readline

N=int(input())

List=[]
for _ in range(N):
    List.append(list(map(int,input().split())))

#DP[현재 도시][방문 비트마스킹]=비용
DP=[[float('inf') for _ in range(2**N)] for _ in range(N)]
'''
dfs
파라미터
-비트마스킹
-현재 위치
'''
ans=float('inf')
def dfs(node,bits):
    global ans
    if bits==2**N-1:
        ans=min(ans,DP[node][bits])
    for i in range(N):
        if List[node][i]!=0 and not bits&(1<<i): #안갔으면
            DP[i][bits|1<<i]=min(DP[i][bits|1<<i],DP[node][bits]+List[node][i])
            dfs(i,bits|1<<i)

DP[0][0]=0
dfs(0,0)

# print(DP)




print(ans)

 

bottom up
DP table을 이용해서 뒤를 돌아보며 내 값을 갱신하는 방법이다. 
이 문제에서는 DP table의 모든 영역을 다 체크하면서 갱신하는 것이 특이하다.
방법은 특정 DP table[현재도시][비트마스킹]= A를 기준으로 해서 DP table 전체에서 for문을 돌린다.-> 이 도시를 가지 않은 비트마스킹을 가진 DP table을 찾아 현재 값을 갱신하는 것이다.

import sys
input=sys.stdin.readline

N=int(input())
List=[]
for _ in range(N):
    List.append(list(map(int,input().split())))

#DP[현재 도시][방문 비트마스킹]=비용
DP=[[float('inf')] *(2**N) for _ in range(N)]
#dfs를 하지 않고 DP bottom up
ans=float('inf')
#초기화 0에서부터 가는 것들.
for i in range(N):
    if List[0][i]: DP[i][1<<i]=List[0][i]

for bits in range(1,1<<N):
    for j in range(N):
        if not (bits&(1<<j)): continue #거기 이미 갔으면 continue
        for k in range(N): #DP테이블에서 가져와서 갱신
            if not (bits&(1<<k)) : continue #거기 이미 갔으면 continue
            if (List[j][k]): DP[k][bits]=min(DP[k][bits], DP[j][bits&~(1<<k)]+List[j][k]);

# print(DP)
for i in range(N):
    ans=min(ans,DP[0][(1 << N) - 1])

print(ans)

top down
이 문제는 사실, top down을 떠올리는 것이 더 옳다.
여기서 원하는 건 최소 cost이다.
top down은 트리에서 점점 끝까지 파고 들어갔다가 다시 돌아오면서 트리 중 특정값을 구하는 방식이다.
여기서 메모이제이션이 효과적인 것을 알 수 있는데, 이미 값이 정해졌다면, '더이상 불러오지 않는다'라는 특징 때문에 그러하다.

이전에 선배가 top down이 더 직관적이야 라고 했을 때 ??엥?? 재귀 호출이 생각하기 더 어려운데... 싶었는데,
이 문제 풀어보니까 약간은 이해가 되었다. 마지막 노드에 다다랐을 때 / 노드값 return / 호출 방식 만 신경쓰면 된다.

top down 재귀는 형태가 대략 이러하다. ?? 경우에 따라 다르지만 그냥 느낌상..
def topdown:
     if 마지막 노드에 다다른 조건:
           return ~~
     if 이미 DP 테이블에 값이 있다면(memoization):
           return 그냥 그거 가져온다.
     #밑에 있는 노드를 호출해서 답 갱신 + 필요하다면 DP 테이블에도 값 갱신
     DP[][]+= 또는 min .. topdown() 
     return 해당 노드값 

import sys
input=sys.stdin.readline
N=int(input())
List=[list(map(int,input().split())) for _ in range(N)]
#DP[현재 도시][방문 비트마스킹]=비용
DP=[[0] *(1<<N-1) for _ in range(N)]
'''
dfs
파라미터
-비트마스킹
-현재 위치
'''

def dfs(node,bits):
    if DP[node][bits]!=0: 
        return DP[node][bits] #이미 최소로 방문. 메모이제이션
    if bits==(1<<(N-1))-1:
        if List[node][0]:
            return List[node][0]
        else: 
            return float('inf')
    dist=float('inf')
    for i in range(1,N):
        if not List[node][i]: 
            continue
        if bits&(1<<i-1): 
            continue#이미 감
        temp=List[node][i]+dfs(i,bits|(1<<(i-1)))
        if dist>temp:dist=temp
    DP[node][bits]=dist

    return dist


print(dfs(0,0))