Chap 18. 그래프이론 - Q43. 어두운 길

  • 0
  • 0
0
0

1. 어두운 길

  • 난이도
  • 풀이 시간
    • 40분
  • 시간 제한
    • 1초
  • 메모리 제한
    • 128MB
  • 출처
    • University of Ulm Local Contest

A. 📜 문제

한 마을은 N개의 집과 M개의 도로로 구성되어 있다. 각 집은 0번부터 N-1번까지의 번호로 구분된다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일하다.

정부에서 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 한다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 한다. 마을의 집과 도로 정보가 주어졌을 때, 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하라.

a. 예를 들면.

예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 하면, 하루 동안 이 가로등을 켜기 위한 비용은 7이다.

b. 입력 조건
  • 첫째 줄에 집의 수 N (1 <= N <= 200,000)과 도로의 수 M (N-1 <= M <= 200,000)이 주어진다.
  • 다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X, Y, Z가 주어지며, 공백으로 구분한다. (0 <= X, Y < N) 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이가 Z라는 의미이다. 단, X와 Y가 동일한 경우는 없으며 마을을 구성하는 모든 도로의 길이 합은 $2^31$보다 작다.
c. 출력 조건
  • 첫째 줄에 일부 가로등을 비활서오하하여 절약할 수 있는 최대 금액을 출력하라.
d. 테스트 케이스
  • 입력 예시

    
    7 11
    0 1 7
    0 3 5
    1 2 8
    1 3 9
    1 4 7
    2 4 5
    3 4 15
    3 5 6
    4 5 8
    4 6 9
    5 6 11
    
    
  • 출력 예시

    
    51
    
    

B. 💡 내 답안

a. 😊 1차 시도 (성공)

"""
Date    : 2021.12.01
Update  : 2021.12.01
Source  : Q43_어두운 길.py
Purpose : 크루스칼 알고리즘 적용하여 해결.
Author  : 김학진 (mildsalmon)
Email   : mildsalmon@gamil.com
"""
# 각 집 사이의 거리가 최소인 길만 가로등을 켠다. -> 크루스칼 알고리즘
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[a] = b
    elif a < b:
        parent[b] = a

n, m = list(map(int, input().split()))

roots = []
# 집의 번호가 0 ~ N-1번으로 주어졌기 때문에 parent의 원소 갯수를 n개만 생성함.
parent = [0] * n
save_cost = 0

for _ in range(m):
    x, y, z = list(map(int, input().split()))
    # 크루스칼 알고리즘을 사용하기 위해(비용 순으로 정렬하기 위해), 길에 대한 정보를 바꿔서 roots 리스트에 집어넣음.
    roots.append((z, x, y))
# 최소 비용의 길부터 탐색하기 위해 첫번째 원소를 기준으로 정렬을 함.
roots.sort()

# 초기 각 집의 부모를 자기 자신으로 초기화함.
for i in range(1, n):
    parent[i] = i

for root in roots:
    cost, a, b = root
    # 부모가 같지 않다면(싸이클이 없다면) union 연산을 함.
    if find_parent(parent, a) != find_parent(parent, b):
        union_parent(parent, a, b)
    else:
        # 문제에서 구하고자 하는 값이 가로등을 비활성하여 절약할 수 있는 금액임.
        # 따라서 가로등을 켜지 않는 경우를 누적하여 합함.
        save_cost += cost

print(save_cost)


c. 🙄 회고

내 풀이

  • 크루스칼 알고리즘이 떠올라서 적용하였다.

C. 🧐 문제 해설

이해한 내용을 바탕으로 작성했습니다.

각 노드(집)들 사이의 길은 이런 방식으로 활성화되고 배제된다.

a. 책 답안

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

참고문헌

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

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