글 읽기 - 1197 와 1922 데이터

wnsqlehlswk 9년 전 0

1197하고 1922 는 같은 mst 구현 문제인데

밑에 코드는 1192는 맞고 1197 은 틀려요

vertex,e=map(int,input().split())
l=[]

#간선의 정보 저장
for i in range(e):
    l+=[list(map(int,input().split()))]


#정점이 속한 집합의 key
#값이 0 아직 선택되지 않은 정점
v=[0]*(vertex+10)

#간선의 정보 가중치 대로 정렬
l.sort(key=lambda a:a[2])


#집합의 집합
sets={}

#요놈이 문제
def has_cycle(v1,v2,cost):
	#두 정점 모두 처음 선택 한것
    #두 정점을 새로운 집합에 넣음
    if v[v1]==0 and v[v2]==0:
       v[v1]=len(sets)+1
       v[v2]=v[v1]
       sets[len(sets)+1]=[v1,v2]

       return False
    
	#싸이클을 만드는 경우
    
    elif v[v1]==v[v2]:
         return True
        
	# 한쪽만 처음 선택하는 경우
    # 집합에 들어가 있지 않은 정점을 집합에 속한 정점에 집어 넣음
    elif v[v1]==0 and v[v2]>0:
         sets[v[v2]]+=[v1]
         v[v1]=v[v2]
         return False

    elif v[v1]>0 and v[v2]==0:
         sets[v[v1]]+=[v2]
         v[v2]=v[v1]
         return False

    #두정점이 서로 다른 집합에 존재 할떄
    #두집합을 병합함
    else:
         s=sets[v[v2]]
         sets[v[v1]]+=s
         sets[v[v2]]=[]
         for i in s:
             v[i]=v[v1]

         return False


#보통의 크루스칼 
def kruskal():
    count=0
    cost=0
    for i in l:
        a,b,c=i
        if has_cycle(a,b,c)==False:
           count+=1
           cost+=c
        if count==vertex-1:  break
    return cost

print(kruskal())

wnsqlehlswk 9년 전 0

파이선3 로 구현 했어요

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

문제

문제

출처

ICPC

1197 와 1922 데이터

wnsqlehlswk 9년 전 0

wnsqlehlswk 9년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말