9/15 개인 문제 풀이 - 1

이코테 p397

import sys
input = sys.stdin.readline

# 크루스칼 알고리즘을 활용하면 되겠군, 유니온 파인드 알고리즘을 사용하자

def find(parent, a):     # 파인드 (루트 노드를 찾는 함수)
  if parent[a] != a:
    parent[a] = find(parent, parent[a])
  return parent[a]

def union(parent, a, b):    # 유니온 (서로 루트노드가 다르면 작은 수쪽으로 합친다)

  a = find(parent, a)
  b = find(parent, b)
  
  if a < b:
    parent[b] = a
  else:
    parent[a] = b

N, M = map(int, input().split())
parent = list(range(0,N))
edges=[]
result = 0

for _ in range(M):
  X,Y,Z = map(int, input().split())
  edges.append((Z,X,Y))
  result += Z

edges.sort() # O(ELogE)

cnt = 0

for edge in edges:
  cost = edge[0]
  v1 = edge[1]
  v2 = edge[2]
  
  if find(parent, v1) == find(parent, v2): # 사이클이 발생
    continue

  union(parent, v1, v2)
  result -= cost  

print(result)
# 크루스칼 알고리즘을 작성해봅시다
# 1. 간선 정렬
# 2. 간선을 하나씩 뽑으면서 사이클이 발생하는지 확인한다.

전형적인 크루스칼 알고리즘 문제였다.

문제조건에서 최대한 !줄일수! 있는 거리를 찾으라고 했는데 최소 거리를 계산해서 디버깅에 애를 먹었다.

문제를 잘읽자.

아 그리고 union 함수를 구현할때 조건절 안의 인수들은 모두 루트노드로 넣어야 제대로 동작한다…!

이것도 디버깅에 애를 먹었다. 기억하도록 하자.

9/17 개인 문제 풀이 - 2

이코테 p398

2887번: 행성 터널

와 답지봐도 이해가 안됨.. 나중에 이해해 보겠습니다