글 읽기 - 엥 이게 아닌가

alftjd1 4년 전 0

안되네요

제가 문제를 잘못이해하고 있는 걸까요?

접근방식 요약

- 깊이 우선 탐색으로 가능한 길을 찾음

- 찾아서 그 길로 갔을때 합을 구함

- 그 값이 현재값보다 작으면 구한값으로 교체함

- 해당 길은 다시 가지않으며 이과정을 반복

import sys
sys.setrecursionlimit(10 ** 6)

input = sys.stdin.readline

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

graph = [[True] * (n + 1) for _ in range(n + 1)]

temp = []

total = 10 ** 10
def scanf(total):
    v = len(temp)
    if v == n:
        tot_ = temp[:]+temp[:1]
        tot = 0
        for i in range(1,n+1):
            tot += lord[tot_[i-1]][tot_[i]]
        if total > tot:
            total = tot
            #print(tot_)
            #print(total)
        temp.pop()
        return scanf(total)
    for i in range(n):
        if v == 0:
            if graph[v][i]:
                graph[v][i] = False
                temp.append(i)
                return scanf(total)
        else:
            if graph[v][i] and lord[v][i] > 0:
                if i not in temp:
                    graph[v][i] = False
                    temp.append(i)
                    return scanf(total)
    if not temp:
        return print(total)
    graph[v] = [True] * n
    temp.pop()
    return scanf(total)

scanf(total)

djm03178 4년 전 0

정확히 코드가 어떻게 돌아가는지는 잘 모르겠지만,

"해당 길은 다시 가지않으며"

는 확실히 틀렸습니다. 그 길을 가는 다른 경로를 봐야 최적을 구할 수 있는 경우도 있을 수 있습니다.

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

문제

문제

출처

ICPC

엥 이게 아닌가

alftjd1 4년 전 0

djm03178 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말