[백준] 1647번 : 도시 분할 계획

 

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

1647번: 도시 분할 계획

전체 그래프를 2개로 나누는데 그 나눠진 그래프 안에서는 서로 다 연결이 돼 있어야 한다는 얘기..... (근데 대체 원숭이🙊 얘기는 왜 나온거지???)

 

📖접근 방법

1. 크루스칼 알고리즘을 이용해서 최소신장 트리를 하나 만듬
2. 그 중에서 가장 비싼 간선을 하나 없앤다 (그래야 최소 비용이 되니까!)
3. 그러면 자연스럽게 그래프가 2개로 분리된다!

 

그리고!

import sys
input = sys.stdin.readline

처음에 파이썬으로 제출했더니 시간초과가 나서 stdin.readline을 사용했더니 통과함!

(똑같은 코드 pypy로 내면 통과함)

 

 

✅ 10-07 추가

이 문제는 아니었고 크루스칼 써서 풀었던 다른 문제였지만! (코테였기 때문에 문제는 안 올림)

간선의 갯수가 E고, 노드의 갯수가 V라고 할 때 시간복잡도는 O(E*logV) 라고 한다. 하마터면 나 노벨상 받을뻔...ㅠㅠㅋㅋㅋㅋㅋ

시간복잡도도 신경써가면서 풀어야겠다는 다짐!😂

 

 

🙋‍♀️ 작성한 코드

import sys

def backjoon1647():
  input = sys.stdin.readline

  #부모노드 확인
  def find_parent(parent, x):
    if parent[x] != x:
      parent[x] = find_parent(parent, parent[x])
    return parent[x]

  #합치기
  def union_parent(parent, x, y):
    x = find_parent(parent, x)
    y = find_parent(parent, y)
    if x < y:
      parent[y] = x
    else:
      parent[x] = y

  #입력받는 부분
  n, m = map(int, input().split())
  graph = []
  for i in range(m):
    a, b, c = map(int, input().split())
    graph.append( (c, a, b) ) #cost로 정렬하려고

  #부모노드 생성 후 자기자신으로 설정
  parent = [0] * (n+1)
  for i in range(n+1):
    parent[i] = i

  graph.sort() #비용 순서로 정렬

  lastCost = 0 #마지막 간선 (나중에 빼려고)
  result = 0

  for c,a,b in graph:
    if find_parent(parent, a) != find_parent(parent, b):
      union_parent(parent, a, b)
      result += c
      lastCost = c
  answer = result - lastCost
  print(answer)