글 읽기 - [MST] 간선의 개수에 대한 질문 (답스포있음)

iron1209 4년 전 0

보통 MST문제면 구성해야 할 간선의 개수가 N-1 입니다

그런데 이 문제는 1번 노드를 제외한 MST를 구성하는게 답인데 거기다 사전에 연결된 간선들을 M개를 줍니다.

그래서 저는 (N-1)-1-M개의 간선만 구성하면 될 줄 예상하였으나 오답이었습니다.

따라서 모든 간선에 대해서 연결 여부를 파악하는 방법으로 정답을 받았는데 아무리 생각해도 (N-1)-1-M개의 간선만 더 구성해도 된다고 생각합니다.

위의 코드는 정답코드고 밑의 코드는 (N-1)-1-M개의 간선을 예상한 코드입니다.

#정답
input=__import__('sys').stdin.readline
def find(x):
    if x==parent[x]:
        return x
    else:
        parent[x]=find(parent[x])
        return parent[x]
def unite(x,y):
    x,y=find(x),find(y)
    parent[y]=x
n,m=map(int,input().split())
edge=[]
parent=list(range(n+1))
for _ in range(m):
    a,b=map(int,input().split())
    unite(a,b)
input()
for i in range(1,n):
    s=list(map(int,input().split()))
    for j in range(i+1,n):
        edge.append((s[j],i+1,j+1))
edge.sort()
cnt,ans=0,0
ansl=[]
#이 아랫부분이 다름
for e in edge:
#이 윗부분이 다름
    if find(e[1])!=find(e[2]):
        ansl.append((e[1],e[2]))
        cnt+=1
        unite(e[1],e[2])
        ans+=e[0]
if cnt==0:
    print(0,0)
else:
    print(ans, cnt)
    for p in ansl:
        print(*p)
        
#
#
#
#
#오답 
input=__import__('sys').stdin.readline
def find(x):
    if x==parent[x]:
        return x
    else:
        parent[x]=find(parent[x])
        return parent[x]
def unite(x,y):
    x,y=find(x),find(y)
    parent[y]=x
n,m=map(int,input().split())
edge=[]
parent=list(range(n+1))
for _ in range(m):
    a,b=map(int,input().split())
    unite(a,b)
input()
for i in range(1,n):
    s=list(map(int,input().split()))
    for j in range(i+1,n):
        edge.append((s[j],i+1,j+1))
edge.sort()
i,cnt,ans=0,0,0
ansl=[]
#이 아래부분이 다름
while cnt<(n-1)-1-m:
#이 윗부분이 다름
    e=edge[i]
    i+=1
    if find(e[1])!=find(e[2]):
        ansl.append((e[1],e[2]))
        cnt+=1
        unite(e[1],e[2])
        ans+=e[0]
if cnt==0:
    print(0,0)
else:
    print(ans, cnt)
    for p in ansl:
        print(*p)

kdr06006 4년 전 0

M개의 간선이 전부 다른 집합에 속해있는 두 노드를 이어주는 것이 아닙니다

같은 집합에 속한 두 노드를 또 이어줄 수도 있습니다.

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

문제

문제

출처

ICPC

[MST] 간선의 개수에 대한 질문 (답스포있음)

iron1209 4년 전 0

kdr06006 4년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말