글 읽기 - (간단한?) 크루스칼 알고리즘 문제입니다ㅠ 4%에서 틀림

larpore2 1년 전 0

안녕하세요, 크루스칼 알고리즘 + 유니온 파인드 사용해서 풀었습니다.

베이직한 크루스칼 알고리즘 코드라 생각했고, 맨 마지막 for문에다 루프 하나가 끝날 때마다 비용을 증가시켜주는 식으로 했는데

백준에 나와있는 테케는 29로 잘 나옵니다.

다만, 4%에서 자꾸 틀리는데 혹시 반례 제시 가능할까요??

import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)

def find (graph,x):  # 우리가 원하는 노드 찾으러 출발~
    if graph[x] != x:
        graph[x] = find(graph,graph[x])
    return graph[x]

def union (graph,A,B):  # 싸이클 형성 안됨과 동시에, 원하는 노드끼리 만났다면 유니온 파인드
    A = find(graph,A)
    B = find(graph,B)
    if A<B:
        graph[B] = A
    else:
        graph[A] = B

N,M,T = map(int,input().split()) # 건물 개수 (노드) , 도로 개수 (간선) , 증가하는 비용
graph = [0]*(N+1) # 그래프 정보 초기화

arr = []
result = 0 # sum은 총 비용 cnt은 생략 가능한 간선 수 result는 최소 비용

for i in range(1,N+1):
    graph[i] = i # 인덱스 넘버가 곧 노드
    
for i in range(M):
    A,B,Cost = map(int,input().split())
    arr.append([Cost,A,B]) # 비용기준 오름차순을 위함
    
arr.sort()

for i in arr:
    Cost,A,B = i
    if find(graph,A) != find(graph,B): # 싸이클이 형성되지 않는다면
        union (graph,A,B)
        result+=Cost
        result+=T # 간선 연결될 때마다 비용 T만큼 추가 증가
        
print(result)  # 백준 테케는 29로 잘 나오는데 반례가 뭘까요

cinador 1년 전 2

반례드립니다.

2 1 10
1 2 3
    
# Output
13
    
# Answer
3

larpore2 1년 전 0

앗... 간선 하나일 때도 더해지고 있었군요... 이런 사소한걸 놓치다니 ㅠ 감사합니다

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

문제

문제

출처

ICPC

(간단한?) 크루스칼 알고리즘 문제입니다ㅠ 4%에서 틀림

larpore2 1년 전 0

cinador 1년 전 2

larpore2 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말