글 읽기 - dfs + 메모이제이션 시간초과 이유가 궁금합니다

tunsi 2년 전 0

dp 에 해당 정점까지 도달하기 위해 필요한 경로의 최소값을 저장하는 방식으로 구현하였는데,

이러한 방식으로는 시간초과를 해결하지 못하는 걸까요? dp 에 앞으로 방문할 정점들의 최단경로를 저장하는 방식으로 바꾸어야하는지,

아니면 다른 실수때문에 시간초과가 발생하는 것인지 궁금합니다!

import sys

N = int(sys.stdin.readline())
board = []
INF = 10**9
for _ in range(N):
    board.append(list(map(int,sys.stdin.readline().split())))

for i in range(N):
    for j in range(N):
        if i==j:
            continue
        if board[i][j] == 0:
            board[i][j] = INF

dp = [[INF] * (2**16) for _ in range(N)]

visited = [0]*N
res = INF
st = 0

def visit(cur,acc,b):
    global res
    if b==(1<<N)-1:
        if res > acc+board[cur][st]:
            res = acc+board[cur][st]
        return
    if dp[cur][b] <= acc:
        return
    dp[cur][b] = acc
    
    for i in range(1,N):
        if visited[i]==0 and board[cur][i]!=INF:
            visited[i] = 1
            visit(i,acc+board[cur][i],b | 1<<i )
            visited[i] = 0

visited[st] = 1
visit(0,0,1)

print(res)﻿﻿

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

문제

문제

출처

ICPC

dfs + 메모이제이션 시간초과 이유가 궁금합니다

tunsi 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말