백준 16302 - Jurassic Jigsaw (Python)

문제 정보

• https://www.acmicpc.net/problem/16302
• MST

---

문제 정리

N개의 DNA가 주어지며, unlikeliness값이 최소가 되도록 트리를 만드는 문제이다. unlikeliness값은 트리를 구성하는 간선들의 가중치 합을 의미하며, 각 간선은 두 DNA에서 문자가 서로 다른 위치의 개수이다.

---

풀이

말이 길지 그냥 MST 만들고 MST를 구성하는 간선을 구하라는 소리이다.
우선 모든 정점 간 간선, 가중치를 구하고, 이 그래프를 기반으로 MST를 구하면 된다.
간선을 만드는데 O(N^2 * 문자열 길이) 만큼 필요하긴 한데 N <= 1,000이라 널널하다.

MST 문제 중에서 직관적인 문제인듯? 풀이도 간선 만들고 MST 딸깍이 전부다.

---

코드

# 백준 16302

import io

input = io.BufferedReader(io.FileIO(0), 1<<18).readline


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


def union(parent, a, b):
    a = find(parent, a)
    b = find(parent, b)
    parent[max(a, b)] = min(a, b)


def Kruskal(V, edge):
    total = 0
    tree = []

    parent = [i for i in range(V+1)]
    edge.sort(key= lambda x: x[2])

    for cur in edge:
        startV, endV, cost = cur
        if find(parent, startV) != find(parent, endV):
            union(parent, startV, endV)
            total += cost
            tree.append([startV, endV])

    return [[total]] + tree


def solve(N, K, dna):
	# 간선 생성
    edge = []
    for i in range(N-1):
        for j in range(i+1, N):
            diff = 0
            for k in range(K):
                if dna[i][k] != dna[j][k]:
                    diff += 1
            edge.append((i, j, diff))
	
    # MST 구하기
    return Kruskal(N, edge)


def main():
    N, K = map(int, input().split())
    dna = []
    for _ in range(N):
        dna.append(input().decode().rstrip())
    
    for i in solve(N, K, dna):
        print(*i)


main()