[Python/백준] 1647. 도시 분할 계획

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

크루스칼 알고리즘

 

https://www.acmicpc.net/problem/1647

---

풀이

1차 접근, 실패

import sys
input = sys.stdin.readline

# 집 N개, 길 M개, 연결 그래프이고, 유지비(가중치) 있음.
# 마을을 두 개로 분할할 건데, 각 분리된 마을은 연결 그래프여야 함.
# 그리고 각 마을은 집이 하나 이상 있어야 함.

# 길을 없앨 건데,
# 1. 분리된 두 마을 사이에 있는 길은 없애고,
# 2. 각 마을 안에서도 임의의 두 집 사이에 항상 경로가 존재하게 하면서
# 길을 더 없앨 수 있음. => 이거는 MST 찾으란 거네.

# 집의 개수와 길의 개수 N, M
# 2번째 줄부터 (x, y, w) 형태로 입력 들어옴.
# 출력 : 두 마을의 없애고 남은 길 유지비의 합의 최소값

n, m = map(int, input().split())
edges = [list(map(int, input().split())) for _ in range(m)]

# MlogM = 대략 100만 * 한자리 수 -> 시간복잡도 OK
# 이거 근데... 저 연산을 브루트 포스로 모든 나누기 경우의 수로 해야 되나?
# => 불가능함. 엄청 큰 시간복잡도를 가질 거임.
# 브루트 포스가 아닌, 뭔가 다른 기막힌 아이디어를 떠올려야 함...

# 일단, 가중치가 큰 길들을 없애고 싶은 건 인정할거임.

여기서 도저히 봐도 모르겠어서 정답 확인함.

아!!!! 위 그림처럼, 일단 MST를 구해놓으면, 거기서 “어떤 간선을 자르든 문제 조건에 맞게 2개의 그래프로 나뉘어진다!!!!!!!”

다만, 문제에서는 최소의 가중치 합을 가지고자 하므로, 가중치가 최대인 간선을 자르면 된다. (반복문 돌면 O(logE)

따라서, 그냥 기존의 MST 코드를 짠 후, 마지막에 간선을 for문 돌면서 max 가중치인 간선의 가중치를 total에서 빼면 완료!!!!

2차 풀이

import sys
input = sys.stdin.readline
def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x]

def union(x, y):
    x_root = find(x)
    y_root = find(y)

    if x_root == y_root:
        return False

    # rank를 낮은 걸 높은거에 붙이는 이유:
    # 그래야 합친 집합 트리의 rank가 유지될 수 있으니까.
    # rank는 직관적으로는 해당 트리의 height라고 볼 수 있으나,
    # 추상적 개념이기에 height와는 다를 수도 있음.
    if rank[x_root] > y_root:
        parent[y_root] = x_root

    elif rank[x_root] < y_root:
        parent[x_root] = y_root

    else:
        parent[y_root] = x_root
        rank[x_root] += 1

    return True

edges.sort(key = lambda x: x[2])
parent = list(range(n + 1))
rank = [0] * (n + 1)
counts = 0
total = 0
weights = []
for x, y, w in edges:
    if union(x, y):
        # 싸이클을 안 만들면: 넣어라!
        counts += 1
        total += w
        weights.append(w)

        if counts == n - 1:
            break
        # 이거 그냥 counts == n - 2일 때 끊고
        # total을 반환해도 정답임!!
        # 왜냐하면, 결국 마지막으로 뽑은 게 그 중 가장 큰 거니까.

print(total - max(weights))

강사님 정답 풀이)

import sys

input = sys.stdin.readline


def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])  # path compression

    return parent[x]


def union(x, y):
    x_root, y_root = find(x), find(y)

    if x_root == y_root:
        return False

    # union by rank
    if rank[x_root] > rank[y_root]:
        parent[y_root] = x_root
    elif rank[x_root] < rank[y_root]:
        parent[x_root] = y_root
    else:
        parent[x_root] = y_root
        rank[y_root] += 1

    return True


n, m = map(int, input().split())
parent = list(range(n + 1))
rank = [0] * (n + 1)
edges = []
total, max_cost, counts = 0, 0, 0

for _ in range(m):
    a, b, c = map(int, input().split())
    edges.append((c, a, b))

edges.sort()

for c, a, b in edges:
    if union(a, b):
        total += c
        counts += 1
        max_cost = max(max_cost, c)  # MST를 이루는 간선 중 가장 비용이 높은 값을 찾기 위함

        if counts == n - 1:
            break

# MST를 만족한 후, 간선 하나를 제거하면 두 개의 마을로 자연스럽게 분리됨
# 이때, 가장 비싼 간선을 제거해야 유지비의 합이 최소가 됨
print(total - max_cost)

---

250228 재풀이

이 경우, 엣지 케이스 n = 2, m = 1을 생각해줘야함!!

 

import sys
input = sys.stdin.readline

# 이 문제는 '사이클' 키워드가 등장했으니, 유니온 파인드를 떠올릴 수 있어야함.
# 사이클은 유니온 파인드의 대표 소재.

def find(x):
    if x != parent[x]:
        parent[x] = find(parent[x])
    return parent[x] # 사실상 x 반환해도 같음

def union(x, y):
    x_root = find(x)
    y_root = find(y)
    # 루트가지고 통합을 해야 두 집합이 통합이 되니까.
    # 중간 꺼 가지고 붙여버리면 끊겨버릴 수 있으니까.

    # 원래 코드에도 있던 부분이었지만, 여기서는 이게 사이클을 판별하는 로직으로도 작동함.
    # 일종의 백트래킹.
    if x_root == y_root:
        return False

    if rank[x_root] > rank[y_root]:
        parent[y_root] = x_root
    # 이렇게 랭크가 큰 노드한테 작은 노드를 붙여주는 이유:
    # 그렇게 붙여야 트리가 최대한 안정적인 구조를 유지해서
    # 높이가 최대한 작게 됨.
    elif rank[x_root] < rank[y_root]:
        parent[x_root] = y_root
    else:
        parent[x_root] = y_root
        rank[y_root] += 1

    return True

n, m = map(int, input().split())
parent = list(range(n))
rank = [0] * n

for t in range(1, m + 1):
    x, y = map(int, input().split())

    # union
    # union이 제대로 되었으면 -> 넘어감
    # union이 제대로 되지 않았으면 -> 사이클 발생 알리고 종료
    if not union(x, y):
        # union이 제대로 되면 True가 반환되어 나가도록 짤 거임.
        print(t)
        break

# 파이썬 if else indentation 테크닉
else:
    print(0)