글 읽기 - [10971] 외판원 순회2 어디가 틀린지 모르겠습니다. ㅠㅠ(파이썬,주석있음)

poroli0119 2년 전 0

입력 예제는 잘 출력되는데 어느 부분때문에 틀렸습니다가 나온느지 잘 모르겠습니다.

봐주시면 정말 감사하겠습니다..!

n = int(input())
nums = [list(map(int, input().split())) for _ in range(n)]

depth = 0
answer = 99999999
visited = []

def recursive_dfs(city, depth, sum_cost, start):
    global answer
    
    # 순회를 마친 경우
    if depth == n:
        answer = min(answer, sum_cost)
        return

    for target in range(0, n):
        # 시작 지점으로 중간에 가지않으며 
        # target 이 city 가 되는 경우를 제외하고 
        # target 이 방문하지 않은 곳인 경우이고
        # city 에서 target 으로 갈때 0인 경우를 제외
        if target != start and target != city and target not in visited and nums[city][target] != 0:
            visited.append(target)
            sum_cost += nums[city][target]
            recursive_dfs(target, depth+1, sum_cost, start)
            sum_cost -= nums[city][target]
            visited.pop()
        
        # 마지막으로 시작지점으로 되돌아가기만 하면 되는 경우
        elif depth == n-1 and target == start:
            visited.append(start)
            sum_cost += nums[city][start]
            recursive_dfs(city, depth + 1, sum_cost, start)
            sum_cost -= nums[city][start]
            visited.pop()

for city in range(n):
    sum_cost = 0
    target = 0
    start = city
    recursive_dfs(city, depth, sum_cost, start)

print(answer)

baba1 2년 전 2

현재 코드는 depth 가 n-1일 때 시작도시로 가는 경로가 존재하는지 확인하고 있지 않습니다. 이를 확인하는 부분을 추가하면 통과합니다.

이와 별개로 현재 코드의 시간복잡도는 O(n ** n) 으로 보이는데, O(n!) 풀이방법도 한번 공부해보시면 좋을것 같습니다.

poroli0119 2년 전 0

답변 너무 감사합니다 말씀해주신대로 시도해보겠습니다..!

n! 으로 하려면 for과정에서 범위를 (o, n) 이 아니게 해야할거 같은데

어떻게 작성해야할지 바로 떠오르진 않네요 이것도 같이 고민해보겠습니다 감사합니다!

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

문제

문제

출처

ICPC

[10971] 외판원 순회2 어디가 틀린지 모르겠습니다. ㅠㅠ(파이썬,주석있음)

poroli0119 2년 전 0

baba1 2년 전 2

poroli0119 2년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말