[코테 스터디] 그래프 이론, 어두운 길

Q43. 어두운 길

🐣문제

한 마을은 N개의 집과 M개의 도로로 구성되어 있습니다. 각 집은 0번부터 N-1번까지의 번호로 구분됩니다. 모든 도로에는 가로등이 구비되어 있는데, 특정한 도로의 가로등을 하루 동안 켜기 위한 비용은 해당 도로의 길이와 동일합니다. 예를 들어 2번 집과 3번 집 사이를 연결하는 길이가 7인 도로가 있다고 해봅시다. 하루 동안 이 가로등을 켜기 위한 비용은 7이 됩니다.

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


입력 조건
첫째 줄에 집의 수와 도로의 수인 N과 M이 주어집니다.
다음 M개의 줄에 걸쳐서 각 도로에 대한 정보 X, Y, Z가 주어지며, 공백으로 구분합니다. 이는 X번 집과 Y번 집 사이에 양방향 도로가 있으며, 그 길이가 Z라는 의미입니다. 단, X와 Y가 동일한 경우는 없으며 마을을 구성하는 모든 도로의 길이 합은 2^31보다 작습니다.

입력 예시
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

🐥풀이

크루스칼 알고리즘 (최소 비용 신장 트리)
가장 적은 비용으로 모든 노드를 연결하기 위한 알고리즘이다.
모든 노드가 연결되면, 사이클이 발생하지 않고 최소 비용으로 각 노드가 연결되어 있다.

for node in nodes:
  x, y, z = node
  if check_team(team, x)!=check_team(team,y):
    union_team(team, x, y)
    result.append(z)

크루스칼 알고리즘을 코드로 구현하면 위와 같다. (여기서 nodes는 각 노드와 사이 비용의 정보를 담고 있고, 비용 기준으로 오름차순 정렬되어 있다. 최소만 구할 것이므로!)

리스트를 돌면서, 두 노드(x, y)와 사이의 비용(z)을 가져온다. 두 노드의 루트 노드가 다르면(집합이 다르다는 말), union_team 함수를 활용하여 두 노드의 집합을 같게 한다. 즉, 두 노드를 연결시킨다. 연결시켰으므로 비용은 추가한다. 이 과정이 끝났을 때의 비용의 합이 최소 비용이 될 것이다.


이 문제에서는 모든 집의 가로등을 밝히되, 최소 비용으로, 최소의 가로등만 밝히려고 하고 있다. 따라서 크루스칼 알고리즘을 사용하면 된다. 집과 거리 비용 정보를 거리 비용 기준으로 오름차순 정렬하여, 크루스칼 알고리즘 코드를 활용하면 최소 가로등의 비용을 구할 수 있다.

문제에서는 절약하는 최대 비용을 구해달라고 했으므로 (모든 비용)-(최소 비용)의 결과를 출력해주면 된다.

🐓코드

# 입력값
n, m = map(int, input().split())  # 도시개수, 도로개수
roads = [list(map(int, input().split())) for _ in range(m)]

# 도로비용 기준으로 오름차순 정렬
roads = sorted(roads, key=lambda x:x[2])  

# 그룹 초기화
team = [0]*(n)
for i in range(n): team[i]=i

# 루트 검사
def check_team(team, x):
  if team[x]!=x:
    return check_team(team, team[x])
  return team[x]

# 그룹 합치기
def union_team(team, a, b):
  a, b = check_team(team, a), check_team(team, b)
  if a>b:
    team[a]=b
  else:
    team[b]=a


result, total = [], 0

# 크루스칼 (최소비용신장트리)
for road in roads:
  x, y, z = road
  
  if check_team(team, x)!=check_team(team,y):
    union_team(team, x, y)
    result.append(z)

  # 전체 도로 비용을 구하기 위함
  total += z

# (전체 도로 비용) - (최소신장트리 비용)
print(total-sum(result))

⭐2022.05.12

크루스칼 알고리즘..! 처음 스터디에서 공부할 때는 이해하기 무지 힘들었는데, 이해하고 나니까 활용할 때 문제가 쉬워진다. (우왕) 얼른 더 적응해야겠다 ㅎ.ㅎ