[파이썬] 백준 1647 : 도시 분할 계획 (골드4)

[파이썬] 백준 1647 : 도시 분할 계획 (골드4)

 

1647번: 도시 분할 계획

 

---

문제

---

풀이

0. 방향성 생각

도시가 최소한의 비용으로 연결되는 경우이므로 최소 스패닝 트리를 생각한다.

여기서 간선의 가중치가 가장 높은 부분을 제거하면 마을이 두 개로 나누어진다.

 

1. 입력 받기

import sys
input = sys.stdin.readline

house,path = map(int,input().split())
graph = []

for i in range(path):
    a,b,cost = map(int,input().split())
    graph.append((a,b,cost))
graph.sort(key=lambda x:x[2])

입력을 받아서 graph에 넣어주고 가중치가 작은 노드부터 택해야하므로 cost에 대해서 정렬해준다.

 

2. 부모 노드 찾는 함수, 트리 합치는 함수 정의

parent = [i for i in range(house+1)]

def find_parent(parent,x):
    if parent[x] != x :
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,x,y):
    x = find_parent(parent,x)
    y = find_parent(parent,y)
    if x < y :
        parent[y] = x
    else:
        parent[x] = y

현재 자신이 가르키는 부모가 자신과 다르면 재귀적으로 호출해서 parent를 업데이트 해준다.

 

3. 정답 출력

min_cost,path_count = 0,0
for (a,b,cost) in graph:
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        min_cost += cost
        path_count += 1
        if path_count == (house-1):
            min_cost -= cost
            path_count -= 1
            break

print(min_cost)

노드 a,b와 간선의 비용 cost가 주어진다.

사이클이 생기지 않게 find_parent를 사용한다.

부모 노드가 서로 다르면 서로 합칠 수 있다. union_parent를 사용해서 a 노드가 포함된 그래프와 b 노드가 포함된 그래프를 합친다.

간선을 노드의 개수인 house-1 만큼 선택했으면 MST가 끝난다.

이 때 마지막으로 탐색한 cost를 빼주면 두 개의 마을로 분할하고 최소 비용을 얻을 수 있다.

---

전체코드

import sys
input = sys.stdin.readline

house,path = map(int,input().split())
graph = []

for i in range(path):
    a,b,cost = map(int,input().split())
    graph.append((a,b,cost))
graph.sort(key=lambda x:x[2])

parent = [i for i in range(house+1)]

def find_parent(parent,x):
    if parent[x] != x :
        parent[x] = find_parent(parent,parent[x])
    return parent[x]

def union_parent(parent,x,y):
    x = find_parent(parent,x)
    y = find_parent(parent,y)
    if x < y :
        parent[y] = x
    else:
        parent[x] = y

min_cost,path_count = 0,0
for (a,b,cost) in graph:
    if find_parent(parent,a) != find_parent(parent,b):
        union_parent(parent,a,b)
        min_cost += cost
        path_count += 1
        if path_count == (house-1):
            min_cost -= cost
            path_count -= 1
            break

print(min_cost)