글 읽기 - 반례 혹은 코드의 잘못된 점이 있을까요?(질문 반례 다 됨)

whiteleo100 1년 전 0

1에서 시작을 해서 가장 최소의 값부터 탐사를 시작합니다.

연결이 끊겨서는 안 되니 지나온 길을 표시하면서 갑니다. 연결 값은 저장해 줍니다.

그 연결에서 탐색이 끝나면 node를 remove 해줘서 다른 길로 갔을때 입력값이 더 작으면 탐사합니다.

9%에서 바로 틀렸다고 나오는데... 어디가 틀렸는지 잘 모르겠습니다...

최소로 탐색을하고, 모든 노드가 연결되어있고... 라고 생각을 하는데요

여러 반례를 생각해보고 또 찾아봤지만 전혀 나오지 않습니다.

import sys,collections
sys.setrecursionlimit(10**9)
input = sys.stdin.readline


V,E = map(int, input().split())
v = [float('inf') for _ in range(V + 1)]
edges = collections.defaultdict(list)

for _ in range(E):
    a,b,c = map(int, input().split())
    edges[a].append([b,c])
    edges[b].append([a,c])
def dfs(node:int,visited:set) -> None:
    for n,c in sorted(edges[node],key = lambda x:x[1]):
        if c < v[n] and n not in visited:
            v[n] = c
            visited.add(n)
            dfs(n,visited)
            visited.remove(n)
dfs(1,set([1]))
print(sum(v[2:]))

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

문제

문제

출처

ICPC

반례 혹은 코드의 잘못된 점이 있을까요?(질문 반례 다 됨)

whiteleo100 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말