글 읽기 - [Python3] 2098 - 외판원순회 시간초과 질문입니다.

occidere 7년 전 1

파이썬으로 외판원 순회 문제를 풀어보는데 C나 Java로는 넉넉하게 통과한 알고리즘이 파이썬3로는 시간초과의 늪에서 벗어날 기미를 안보입니다...

사용한 알고리즘은 많은 분들이 이미 이용하신 정석적인 방법으로, 재귀를 이용한 비트마스킹+DP 방식입니다.

정녕 파이썬3에선 이 방식으로는 안되는 것인가요 ㅠㅠ

n = int(input()); map = []; dist=[]; INF = 987654321

def tsp(cur, visit):
    curDist = dist[cur][visit]
    if not curDist: return curDist
    if visit==(1<<n)-1: return map[cur][0]
    
    dist[cur][visit] = INF
    for i in range(n):
        if map[cur][i] and not (visit&(1<<i)):
            dist[cur][visit] = min(dist[cur][visit], tsp(i, visit|(1<<i)) + map[cur][i])
    return dist[cur][visit]

#main
for i in range(n):
    map.append([int(k) for k in input().split()])
    dist.append([INF for k in range(1<<n)])
print(tsp(0, 1))

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

[Python3] 2098 - 외판원순회 시간초과 질문입니다.

occidere 7년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말