[알고리즘/백준] 1922번 네트워크 연결 Python 파이썬

 

이번 문제는 어려워서 풀이만 하는데도 1시간 넘게 걸린 문제였습니다.

 

 

모든 컴퓨터가 연결했을 때 최소 비용을 구하는 문제로 처음 문제를 보고 생각한 풀이 방법은 가중치가 적은 순으로 나열해연결할까 생각했는데 그 경우 어떻게 모든 컴퓨터가 연결되었는지 확인 방법이 생각 안났습니다. 그래서 두번째는 한 점을 잡아서 작은 가중치로 타고 타고 연결할까 했지만 그 경우 최소값을 구할 수 없다는 점이 있었습니다. 

 

결국 머리 싸매다가 다른 분의 풀이를 찾아봤고 새로운 알고리즘에 대해 알게 되었습니다. (대개 문제가 안 풀리면 기존에 알고 있는 알고리즘으로는 안 풀리는 거 같습니다ㅠㅠ) 이번에 알게된 알고리즘은 "최소 스패닝 트리"하는 알고리즘으로 이해하는데는 해당 블로그(https://www.crocus.co.kr/733) 를 통해 잘 이해할 수 있었습니다.

 

일단 먼저 다음과 같은 코드로 통과하였습니다.

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
computer_list = [list(map(int, input().split())) for _ in range(m)]
computer_list = sorted(computer_list, key=lambda k:k[2])
parent =[i for i in range(0,n+1)]
answer = 0

def find(x):
   if x==parent[x]:
      return x
   parent[x]=find(parent[x])
   return parent[x]

def union(x,y):
    x,y=find(x),find(y)
    parent[x]=y

for s, e, w in computer_list:
    if find(s) == find(e):
        continue
    else:
        answer += w
        union(s,e)
        
print(answer)

 

위 블로그 글을 보고 처음에 구상한 풀이 방식이랑 비슷하다고 느꼈습니다. 다만, 방식은 이해했는데 이를 코드로 짜려고 하니 막막했습니다. 그래서 코드 풀이도 참고했는데 간단하게 보이지만 복잡했습니다. 이해하는데 머리가 안 돌아갔고 일일이 적어보다가 결국 로그를 찍어보았습니다. 

 

 

해당 코드를 좀더 쉽게 이해할려면 제일 좋은 것은 부모트리를 저장하는 배열이 각 값이 들어올 때마다 어떻게 변하는지 확인하는 게 좋은 것 같습니다. 

 

 

피피티로 값을 정리하면서 이해하였는데 위의 정렬된 값이 순차적으로 들어온다고 할 때 부모 노드 배열이 어떻게 바뀌는지 적어놓았습니다. 여기서 주의할 점은 O 경우 둘의 부모가 다르다고 판별해서 union 함수를 통해서 연결해주는 경우이고 X 경우는 둘의 부모가 같다고 판별해서 연결을 안해준 경우입니다. 이때, 연결을 안해주어도 find 함수에서도 부모 노드 배열 값이 바뀐다는 것입니다.

 

워낙 단계가 많고 복잡해서 제일 좋은 것은 예제를 바탕으로 직접 하나하나 따라가보는게 좋을 거 같습니다.  

갈수록 어려워져서 걱정이지만 빨리 게임 문제집 끝내고 싶습니다.