한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다.
정부는 일부 가로등을 비활성화하되, 마을에 있는 임의의 두 집에 대하여 가로등이 켜진 도로만으로도 오갈 수 있도록 만들고자 합니다. 결과적으로 일부 가로등을 비활성화하여 최대한 많은 금액을 절약하고자 합니다. 마을의 집과 도로 정보가 주어졌을 때 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 출력하는 프로그램을 작성하세요
입력 예시 N M (집의수 N, 도로의수 M) X Y Z (X번집과 Y번집 사이의 도로(비용) Z 일부 가로등을 비활성화하여 절약할 수 있는 최대 금액을 구하는데
제 생각에는 보자마자 신장트리 문제 같았습니다. 임의의 두 집에 대하여 가로등이 켜진 도로만으로 오갈 수 있으니 이제 크루스칼 알고리즘을 사용하면 됩니다. 하지만 도로의 전체 비용을 구하는 것이 아닌 절약하는 비용입니다.
그러니 전체 가로등을 켜는 비용에 최소 비용을 빼면 되겠네요
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#특정 원소가 속한 집합을 찾기
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 = map(int,input().split())
parent = [0]*(n+1) #부모 테이블 초기화
#모든 간선을 담을 리스트와 최종 비용을 담을 변수
edges = []
result = 0
#부모 테이블상에서, 부모를 자기 자신으로 초기화
for i in range(1,n+1):
parent[i] = i
#모든 간선에 대해서 정보를 입력받기
for _ in range(m):
x, y, z = map(int,input().split())
#비용순으로 정렬하기 위해서 튜플의 첫 번째 원소를 비용으로 설정
edges.append((z,x,y))
시작은 전과 비슷합니다. 일단 원소가 속한 집합(루트노드)를 찾고, 두 원소가 속한 집합을 합치는 함수를 만들고
값을 입력받고 부모 노드를 자기 자신으로 초기화를 합니다.
이때 간선을 입력받을때 비용을 기준으로 하기 위해서 z를 먼저 받습니다.
1
2
3
#간선을 비용순으로 정렬
edges.sort()
total = 0 #전체 가로등 비용
그러면 간선은 z를 기준으로 먼저 정렬이 이루어지고 전체 입력받을 가로등 비용은 0으로 초기화를 합시다.
그 다음 최소비용으로 이루어지는 값 result는 위에서 초기화를 합니다.
1
2
3
4
5
6
7
8
9
10
#간선을 하나씩 확인하며
for edge in edges:
cost, a, b = edge
total += cost
#사이클이 발생하지 않는 경우에만 집합에 포함
if find_parent(parent, a) != find_parent(parent, b):
union_parent(parent, a, b)
result += cost
print(total - result)
그리고 간선을 하나씩 확인하면서 사이클이 발생하지 않는 경우에만(두 집합의 부모가 같지 않을 경우)에만 합치고 비용을 계산하여 result를 갱신을 하고
최종적으로 전체 비용에서 result를 빼는 것으로 출력을 합니다.
Comments powered by Disqus.