[골드4] 1922번 : 네트워크 연결

🛠 문제

https://www.acmicpc.net/problem/1922

👩🏻‍💻 해결 방법

전형적인 최소 비용 유형의 문제로, 따로 응용 필요 없이 크루스칼 알고리즘만을 이용해 답을 구할 수 있었다
다만 효율성이 떨어지기 때문에 다음에 풀 때는 효율성을 고려한 풀이로 꼭 풀어야겠다

소스 코드

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

n = int(input())
m = int(input())
parent = [0] * (n + 1)

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

edges = []
result = 0

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

edges.sort()

for edge in edges:
  cost, a, b = edge
  if find_parent(parent, a) != find_parent(parent, b):
    union_parent(parent, a, b)
    result += cost

print(result)

💡 다른 사람의 풀이

n = int(input())
m = int(input())

costs = [list(map(int, input().split())) for _ in range(m)]

# 비용을 기준으로 오름차순 정렬 
costs.sort(key=lambda x: x[2])

# set 자료구조 이용
s = {costs[0][0]}

# 정답
answer = 0

# set에 모든 컴퓨터가 들어오기전까지 돌리기
while len(s) != n:
    for idx, cost in enumerate(costs):
    	# 양쪽 node가 이미 자료구조에 들어있다면 무시
        if cost[0] in s and cost[1] in s:
            continue
            
        # 둘중 하나의 노드만 들어가있을 경우    
        if cost[0] in s or cost[1] in s:
            # 비용 추가
            answer += cost[2]
            
            # set자료구조에 update반영
            s.update([cost[0], cost[1]])
            
            # 한번 훑고 나온 노드 연결 정보는 -1로 바꾸어줘서 다음번에 영향을 미치지 않는다
            costs[idx] = [-1, -1, -1]
            
            # 최소비용을 담았으면 탈출하고 다시 처음부터 훑어서 방금 연결된 노드와 연결된 노드를 계속 찾는다
            break

print(answer)