[그래프] - 도시 분할 계획(크루스칼)

n개의 노드와 m개의 간선을 사용해서 2개의 그룹으로 만드는 최소신장트리를 구하라.

크루스칼 알고리즘을 사용하면 될것 같으며 최소신장 트리가 완성이 되면 뒤 최소 신장 트리의 집합내부에 가장 큰 비용을 가진 간선을 제외하고 모두 더하면 될것 같다..!

 

나의 코드

def union(parent,a,b):
    a=find_parent(parent,a)
    b=find_parent(parent,b)
    if a>b:
        parent[a]=b
    else:
        parent[b]=a

def find_parent(parent,x):
    if parent[x] != x:
        parent[x]=find_parent(parent,parent[x])
    return parent[x]


n,m=map(int,input().split())
edges=[]

parent=[0]*(n+1)

for i in range(n+1):
    parent[i]=i


for _ in range(m):
    a,b,c=map(int,input().split())
    edges.append((c,[a,b]))

edges.sort()



res=[]
for i in range(m):
    if find_parent(parent,edges[i][1][0])==find_parent(parent,edges[i][1][1]):
        continue
    else:
        res.append(edges[i])
        union(parent,edges[i][1][0],edges[i][1][1])
        
res.pop()

S=0
for i in range(len(res)):
    S+=res[i][0]
print(S)

전형적인 크루스칼 알고리즘이다.

최소 신장트리를 만든 후 최소신장트리집합중 가장 큰 비용을 뺸 합을 출력 하면 되었다 !!!

 

 

 

 

정답 코드

# 특정 원소가 속한 집합을 찾기
def find_parent(parent, x):
    # 루트 노드가 아니라면, 루트 노드를 찾을 때까지 재귀적으로 호출
    if parent[x] != x:
        parent[x] = find_parent(parent, parent[x])
    return parent[x]

# 두 원소가 속한 집합을 합치기
def union_parent(parent, a, b):
    a = find_parent(parent, a)
    b = find_parent(parent, b)
    if a < b:
        parent[b] = a
    else:
        parent[a] = b

# 노드의 개수와 간선(Union 연산)의 개수 입력받기
v, e = map(int, input().split())
parent = [0] * (v + 1) # 부모 테이블 초기화

# 모든 간선을 담을 리스트와, 최종 비용을 담을 변수
edges = []
result = 0

# 부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1, v + 1):
    parent[i] = i

# 모든 간선에 대한 정보를 입력받기
for _ in range(e):
    a, b, cost = map(int, input().split())
    # 비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
    edges.append((cost, a, b))

# 간선을 비용순으로 정렬
edges.sort()
last = 0 # 최소 신장 트리에 포함되는 간선 중에서 가장 비용이 큰 간선

# 간선을 하나씩 확인하며
for edge in edges:
    cost, a, b = edge
    # 사이클이 발생하지 않는 경우에만 집합에 포함
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
        result += cost
        last = cost

print(result - last)

 

간선을 확인하며 최종 출력값인 비용을 구하는 로직은 다르지만 알고리즘 접근과 전체적인 구성은 비슷하다 !
그래도 정답 코드가 처럼 하나의 간선을 반복문 내부에서 다 푼다음 find_parent함수를 사용하는것이 더 코드도 짧고 더 좋은것 같다.

 

음.. 그치면 크루스칼 알고리즘을 알아 차린뒤 순차적으로 접근을 해본 결과 나의 코드가 더 사고적, 직관적으로 이해하기 쉬운 코드라고 생각한다...ㅇㅅㅇ