백준 16302 - Jurassic Jigsaw (C++)

문제

• 문제 링크

  
   BOJ 16302 - Jurassic Jigsaw 
  

• 문제 요약

mst 역추적

• 제한

TL : $1$ sec, ML : $512$ MB




$1 ≤ N ≤ 1,000$

$1 ≤ k ≤ 10$

알고리즘 분류

• 그래프 이론(graphs)
• 최소 스패닝 트리(mst)

풀이

그냥 기본 mst 문제다.
임의의 문자열 쌍마다 서로 다른 문자 수 만큼 가중치를 메긴 뒤 mst를 돌려주면 된다.

전체 코드

#include<bits/stdc++.h>
using namespace std;
 
struct E
{
    int x, y, w;
    bool operator<(E& e) { return w < e.w; }
};
vector <E> Eg, an;
int n, k, i, P[1001];
 
int f(int p) { return P[p] = P[p] == p ? p : f(P[p]); }
int main()
{
    ios_base::sync_with_stdio(0); cin.tie(0);
    iota(P, P + 1001, 0);
    cin >> n >> k;
    for (vector <string> V(n); n--; i++)
    {
        cin >> V[i];
        for (int j{}, c{}; j < i; c = 0, j++)
        {
            for (int l{}; l < k; l++)
                c += V[j][l] != V[i][l];
            Eg.push_back({ j, i, c });
        }
    }
    i = 0; sort(Eg.begin(), Eg.end());
    for (auto& [x, y, w] : Eg)
    {
        n = f(x), k = f(y);
        if (n ^ k)
        {
            an.push_back({ x, y, 0 });
            i += w;
            n > k ? P[n] = k : P[k] = n;
        }
    }
    cout << i << '\n';
    for (auto& [x, y, w] : an)
        cout << x << ' ' << y << '\n';
}

comment

끝