알고리즘 / 자료구조’ 시리즈

[이.취.코] [백준] Chap 10. 그래프 이론 - 도시 분할 계획

  • 0
  • 0
0
0

1. 도시 분할 계획

A. 문제

위 백준 사이트에 접속하여 문제를 확인해주세요.

a. 입력 조건
  • 집의 개수 N, 길의 개수 M
    • 2 <= N <= 100,000
    • 1 <= M <= 1,000,000
  • M줄에 걸쳐 길의 정보 A, B, C가 공백으로 구분되어 주어진다.
    • A번 집과 B번 집을 연결하는 길의 유지비가 C(1<=C<=1,000)이다.
c. 출력 조건
  • 길을 없애고 남은 유지비 합의 최솟값
d. 테스트 케이스
  • 입력 예시

    
    7 12
    1 2 3
    1 3 2
    3 2 1
    2 5 2
    3 4 4
    7 3 6
    5 1 5
    1 6 2
    6 4 1
    6 5 3
    4 5 3
    6 7 4
    
    
  • 출력 예시

    
    8
    
    

B. 내 답안


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, m = list(map(int, input().split()))  
array = []  
parent = [0] * (n+1)  
result = 0  
last = 0  
  
for i in range(1, n+1):  
    parent[i] = i  
  
for i in range(m):  
    a, b, c = list(map(int, input().split()))  
    array.append([c, a, b])  
  
array.sort()  
  
for i in range(m):  
    c, a, b = array[i]  
  
    if find_parent(parent, a) == find_parent(parent, b):  
        continue  
 else:  
        union_parent(parent, a, b)  
        result += c  
        last = c  
    print(parent[1:])  
  
print(result-last)  
  
# 22분 46초 / Non-Pass / 마지막 last = c를 생각 못함. (마을을 2덩어리로 나눈다고 했는데, 길 하나만 연결된 마을 2개인 줄 알았다.)

a. 회고

풀이

  • 조건
    • 유지비가 최소로 들어가는 길만 남긴다.
    • 집들은 다 연결되어 있다.
  • 위 조건을 보고 크루스칼 알고리즘이 떠올랐다.

반성

  • 다만, 문제를 제대로 읽지 않아서 마을 2개로 분리한다는 것을 마을 2개는 1개의 도로로 연결되어 있다라고 해석해버렸다.

결론

  • 문제를 똑바로 읽자.

C. 문제 해설

전체 그래프에서 2개의 최소 신장 트리를 만들어야 한다는 것이다. 최소한의 비용으로 2개의 신장 트리로 분할하는 방법은 다음과 같다.

크루스칼 알고리즘으로 최소 신장 트리를 찾은 뒤에 최소 신장 트리를 구성하는 간선 중에서 가장 비용이 큰 간선을 제거하는 것이다.

a. 책 답안

python-for-coding-test/8.py at master · ndb796/python-for-coding-test (github.com)

참고문헌

나동빈, "이것이 취업을 위한 코딩 테스트다 with 파이썬", 초판, 2쇄, 한빛미디어, 2020년

0분전
작성된 댓글이 없습니다. 첫 댓글을 달아보세요!
    댓글을 작성하려면 로그인이 필요합니다.