[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
-
댓글 입력