글 읽기 - 파이썬) 그리디로 풀어보려고 했는데 잘 안 되네요...

jwjung0907 2년 전 1

제가 처음 생각이 들었던 것은 트리는 간선이 V - 1개 이니까

간선 E 개를 내림차순으로 정렬해서 그 가중치를 가진 간선과 연결된 정점이 연결된 간선이 2개 이상인지(간선을 제거 했을 때 트리를 만들 수 있는지) 확인해서 그 간선을 제거해주는 방향으로 하면 되겠다 싶었는데, 틀렸습니다를 받네요..

반례가 나올만한 상황이 현재 제거할 수 있는 간선을 제거했을 때 어떤 정점이 제거할 수 있었던 간선을 제거하지 못하게 됨으로써 발생할 수 있을 것 같기도 한데, 저로써는 잘 떠오르지 않네요...

반례나 오류 지적해주시면 정말 감사할 것 같습니다..

import sys
import heapq

V, E = map(int, input().split())
connected = [0] * (V + 1)
heap = []
total_w = 0
for _ in range(E):
    A, B, C = map(int, sys.stdin.readline().split())
    connected[A] += 1
    connected[B] += 1
    heapq.heappush(heap, (-C, A, B))
    total_w += C

while E > V - 1:
    C, A, B = heapq.heappop(heap)
    if connected[A] > 1 and connected[B] > 1:
        connected[A] -= 1
        connected[B] -= 1
        total_w += C
        E -= 1

print(total_w)

dk10211 2년 전 3

반례 드립니다

6 7

1 3 2

1 2 5

2 3 1

3 4 10

3 5 9

4 6 8

5 6 7

정답은 27인데 작성자님 코드는 23이 나와요

값을 보면 4,5,6 정점과 1,2,3 정점이 서로 나뉘어져 있어서 트리가 아닌데 1,2,3부분에는 사이클까지 생기죠

jwjung0907 2년 전 1

@dk10211

답변 감사드립니다.

고립될 수 있는 경우가 확실히 있네요..

아마 간선이 제거 가능한 간선인지 확인하는 부분을 넣어야 할 것 같습니다.

다시 한번 감사드립니다!

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

문제

문제

출처

ICPC

파이썬) 그리디로 풀어보려고 했는데 잘 안 되네요...

jwjung0907 2년 전 1

dk10211 2년 전 3

jwjung0907 2년 전 1

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말