[Python3] 비트 마스크와 재귀를 이용한 코드를 짰는데 왜 출력 값이 안 나오는지 모르겠습니다.

조회수 948회

제가 지금 풀고 있는 문제는 백준 온라인 저지 2098번 외판원 순회입니다. 이 문제를 푸는 제일 일반적인 방법은 비트마스크와 다이나믹 프로그래밍으로 알고 있는데요. 저도 일단 그렇게 짜긴 했는데 아예 출력값이 없는 상황입니다. 왜 출력 값이 없는 지, 문제를 맞게 풀려면 어떻게 메모이제이션을 하는 게 효율적인지 알고 싶습니다.

# https://www.acmicpc.net/problem/2098

from math import inf
from sys import stdin,setrecursionlimit

setrecursionlimit(10**9)

def DP(now, visited):
    global dpList, visitedAll,w
    if now == 0:
        #시작 점 초기화
        if visited == 1:
            dpList[now][visited] = 0
        #시작한 상황인데 이미 방문한 곳이 1이상인 이상한 경우 제외
        else :
            dpList[now][visited] = inf
    if dpList[now][visited] != None:
        pass
    else:
        #여기서 부터는 아직 방문 안한 거
        tempVal = inf
        visitedExceptNow = visited & (~now)
        for i in range(n):
            if (visitedExceptNow >> i) & 1:
                before = i
                tempVal = min(tempVal, DP(before,visitedExceptNow)+w[before][now])
        dpList[now][visited] = tempVal
    return dpList[now][visited]

n = int(stdin.readline())
w = list()
for _ in range(n):
    w.append([inf if int(i) == 0 else int(i) for i in stdin.readline().split()])
dpList = [[None for _ in range(1 << n)] for __ in range(n)]
visitedAll = (1 << n) - 1
aList = list()
for i in range(1,n):
    aList.append(DP(i,visitedAll)+w[i][0])
print(min(aList))
  • (•́ ✖ •̀)
    알 수 없는 사용자

1 답변

  • # https://www.acmicpc.net/problem/2098
    # none 과 int는 같은 리스트 있는 상태에서 min을 쓸 수 없다.
    # 시간초과 1번
    from sys import stdin
    
    n = int(stdin.readline())
    start = 0
    visitedAll = (1 << n) - 1
    
    w = [[] for _ in range(n)]
    for i in range(n):
        for j in map(int,stdin.readline().split()):
            if j == 0:
                w[i].append(None)
            else :
                w[i].append(j)
    
    dpList = [[ -1 for _ in range(1 << n)] for __ in range(n)]
    for j in range(1 << n):
        if j == 1:
            dpList[0][j] = 0
        else :
            dpList[0][j] = None
    
    def DP(now: int, visited: int) -> int:
        global dpList
        if dpList[now][visited] == -1:
            compareList = list()
            visitedBefore = visited & (~(1 << now))
            for i in range(visitedBefore):
                if (visitedBefore >> i) & 1:
                    before = i
                else:
                    continue
                if DP(before, visitedBefore) is not None and w[before][now] is not None:
                    compareList.append(DP(before, visitedBefore)+w[before][now])
            if compareList:
                dpList[now][visited] = min(compareList)
            else:
                dpList[now][visited] = None
            return dpList[now][visited]
        else:
            return dpList[now][visited]
    
    endPointList = list()
    for last in range(1,n) :
        if DP(last, visitedAll) is not None and w[last][start] is not None:
            endPointList.append(DP(last, visitedAll)+w[last][start])
    print(min(endPointList))
    

    자문 자답입니다. bitmask에 대한 이해가 부족하다 보니 잘못된 재귀 조건을 짰네요.

    • (•́ ✖ •̀)
      알 수 없는 사용자
    • 이것도 잘못되었습니다. for i in range(visitedBefore): 에서 visitedBefore 대신에 n을 쓰거나 vistedBefore.bit_length()를 넣어야 합니다. 알 수 없는 사용자 2018.9.18 23:06

답변을 하려면 로그인이 필요합니다.

프로그래머스 커뮤니티는 개발자들을 위한 Q&A 서비스입니다. 로그인해야 답변을 작성하실 수 있습니다.

(ಠ_ಠ)
(ಠ‿ಠ)