Algorithm/이것이 코딩 테스트다/그래프 이론/도시 분할 계획

yellow·2021년 5월 25일
0

알고리즘 문제

목록 보기
23/58

📖문제

동물원에서 막 탈출한 원숭이 한 마리가 세상 구경을 하고 있다. 어느 날 원숭이는 '평화로운 마을'에 잠시 머물렀는데 마침 마을 사람들은 도로 공사 문제로 머리를 맞대고 회의 중이었다.
마을은 N개의 집과 그 집들을 연결하는 M개의 길로 이루어져 있다. 길은 어느 방향으로든지 다닐 수 있는 편리한 길이다. 그리고 길마다 길을 유지하는데 드는 유지비가 있다.
마을의 이장은 마을을 2개의 분리된 마을로 분할할 계힉을 세우고 있다. 마을이 너무 커서 혼자서는 관리할 수 없기 때문이다. 마을을 분할할 때는 각 분리된 마을 안에 집들이 서로 연결되도록 분할해야 한다. 각 분리된 마을 안에 있는 임의의 두 집 사이에 경로가 항상 존재해야 한다는 뜻이다. 마을에는 집이 하나 이상 있어야 한다.
그렇게 마을의 이장은 계획을 세우다가 마을 안에 길이 너무 많다는 생각을 하게 되었다. 일단 분리된 두 마을 사이에 있는 길들은 필요가 없으므로 없앨 수 있다. 그리고 각 분리된 마을 안에서도 임의의 두 집 사이에 경로가 항상 존재하게 하면서 길을 더 없앨 수 있다. 마을의 이장은 위 조건을 만족하도록 길들을 모두 없애고 나머지 길의 유지비의 합을 최소로 하고 싶다. 이것을 구하는 프로그램을 작성하시오.

📝풀이과정

  • 한 마을을 2개의 분리된 마을로 분할하는데, 분리된 마을 안에서는 임의의 두 집 사이에는 무조건 경로가 있도록 만족시키면서 길의 개수는 최소로 유지해야한다는 점에서 '최소 신장 트리' 알고리즘을 사용해야한다고 생각했다.
  1. 일단 마을을 분리하지 말고 크루스칼 알고리즘을 사용하여 최소의 유지비로 모든 집들을 연결할 수 있도록 최소 신장 트리를 구성한다.
  2. 최소 신장 트리를 구성하면서 유지비가 가장 많이 들었던 길을 없애버리면 2개의 마을로 분리되면서 문제에서 주어진 조건(분리된 마을 안에서는 모든 집들이 연결되어있어야 하며, 유지비는 최소여야 한다.)들을 모두 만족시킬 수 있다.

입력 조건

  • 첫째 줄에 집의 개수 N, 길의 개수 M이 주어진다. N은 2 이상 100,000 이하인 정수이고, M은 1 이상 1,000,000 이하인 정수이다.
  • 그다음 줄부터 M줄에 걸쳐 길의 정보가 A, B, C 3개의 정수로 공백으로 구분되어 주어지는데 A번 집과 B번 집을 연결하는 길의 유지비가 C(1 <= C <= 1,000)라는 뜻이다.

출력 조건

  • 첫째 줄에 길을 없애고 남은 유지비 합의 최솟값을 출력한다.

⌨ 코드

# 리스트를 정렬하기 위한 퀵정렬 코드
def quick_sort(a, start, end):
  if end - start <= 0:
    return
  pivot = a[start]
  i = start + 1
  j = end
  while True:
    while a[i] < pivot and i <= end: i += 1
    while a[j] > pivot and j >= start : 
      j -= 1
    if i < j:
     a[i], a[j] = a[j], a[i]
    else:
      a[j], a[start] = a[start], a[j]
      break
  quick_sort(a, start, j - 1)
  quick_sort(a, j + 1, end)

# 특정 집이 속한 집합을 찾기
def find_parent(parent, a):
  if parent[a] != a:
    parent[a] = find_parent(parent, parent[a])
  return parent[a]

# 두 집이 속한 집합을 합치기
def union_parent(parent, a, b):
  a = find_parent(parent, a)
  b = find_parent(parent, b)
  if a > b:
    parent[a] = b
  elif b > a:
    parent[b] = a
    
# n, m을 공백으로 구분하여 입력받기
n, m = map(int, input().split())

# 자신의 부모 노드를 자신으로 초기화
parent = [0] * (n + 1)
for i in range(n + 1):
  parent[i] = i

# 모든 길 정보를 담을 리스트(유지비, 집1, 집2)
roads = []
for _ in range(m):
  a, b, c = map(int, input().split())
  roads.append((c, a, b))

# 유지비 기준으로 오름차순으로 정렬
quick_sort(roads, 0, m - 1)

answer = 0
for road in roads:
  cost, a, b = road
  
  # 한 마을을 구성하는데 cycle이 생기지 않으면
  if find_parent(parent, a) != find_parent(parent, b):
    # 두 집이 속한 집합들을 합친다.
    union_parent(parent, a, b)
    max_cost = cost
    answer += cost

# 마을 2개로 분리하기 위해 유지비가 가장 많이 드는 길 없애기
answer -= max_cost
print(answer)

☺ 느낀점

리스트에 내장되어있는 정렬 메소드를 사용하는데 익숙해져서 막상 퀵정렬 코드를 짜려니 기억이 잘 안나서 한 번 직접 정렬 코드를 작성해서 문제를 풀어보았다.
가끔 라이브러리에 이미 구현된 자료구조나 알고리즘과 관련된 코드들을 한번씩 작성해보는 것이 좋을 것 같다.

profile
할 수 있어! :)

0개의 댓글