[SWEA/Python] 5249 - 최소 신장 트리

 

 

문제

https://swexpertacademy.com/main/learn/course/lectureProblemViewer.do

 

[문제 요약]

 

노드와 간선의 수가 주어지면 이 그래프로 부터 최소 신장트리를 만들고 최소신장트리를 구성하는 간선의 가중치를 모두 더하는 문제다.

 

 

풀이

 

[풀이]

 

입력으로 받은 값에서 가중치를 2차원 리스트에 저장했고, 그 외의 값들은 최댓값인 10보다 큰 11로 저장했다.

 

그리고 방문한 지점은 vistied에 True, False로 저장해 구분했다. 처음 시작은 0번 노드에서 시작을 했고, 가중치를 0으로 주었다.

 

이후 노드의 수 만큼 for문을 돌려 방문을 하지 않은 노드 중 가중치가 가장 노드를 선택해 가중치를 탐색하도록 코드를 작성했다.

 

 

Code

 

 

def MST_PRIM(node_s):
    key=[11]*(V+1) # key 값은 최댓값보다 큰 값으로 초기화
    visited=[False]*(V+1) # 방문한 지점들을 저장할 list
    key[node_s]=0 # 초기 시작 위치의 가중치를 0으로 초기화
    for _ in range(V+1):
        minval=11
        for i in range(V+1):
            if not visited[i] and key[i]<minval: # 방문하지 않은 노드 중 간선의 가중치가 가장 작은 노드를 찾음
                minval=key[i]
                mindex=i
        visited[mindex]=True # 방문처리
        for i in dic[mindex]:
            if not visited[i] and lst[i][mindex]<key[i]: # 선택한 노드의 주변 노드들의 가중치를 비교하고 작은 값을 저장 
                key[i]=lst[i][mindex]
    print(f'#{tc} {sum(key)}')

for tc in range(1,1+int(input())):
    V,E=map(int,input().split())
    dic=dict()
    lst=[[11]*(V+1) for _ in range(V+1)]
    for i in range(E):
        n1,n2,w=map(int,input().split())
        lst[n1][n2]=w
        lst[n2][n1]=w
        if n1 in dic: #노드와 연결된 노드들을 저장한  dic생성
            dic[n1].append(n2)
            if n2 in dic:
                dic[n2].append(n1)
            else :
                dic[n2]=[n1]
        else:
            dic[n1]=[n2]
            dic[n2]=[n1]
    MST_PRIM(0)

 

---

 

처음에 최소값만 구하면 될 줄 알았는데 간선이 모두 연결이 되어 있어야 해서 생각보다 까다로웠다. 문제를 풀면서 다시 최소신장트리를 구하는 방법에 대해 생각을 정리할 수 있었다.