백준 16202 - MST 게임

문제 링크입니다 https://www.acmicpc.net/problem/16202

16202번: MST 게임

 

최소 스패닝 트리 문제였습니다.

 

문제 조건

각 라운드마다 가중치가 가장 작은 선을 없앤뒤, 남은 간선을 통해서 최소 스패닝 트리를 돌립니다. 그후에 모든 점이 연결 되었는지 확인하고 답을 출력하는 문제입니다.

 

문제 접근 방법

 

1. 구조체를 만들어서 출발 지점, 도착 지점, 가중치를 담을 수 있도록 한뒤, 구조체 백터를 구현합니다.

2. N,M,K를 입력 받은뒤, x,y 값을 입력받고, 백터에다가 입력합니다.

3. 가중치가 가장 작은 선을 하나 없앱니다.(cnt가 0일때는 없애지 않습니다).

4. 최소 스패닝 트리를 구현해 트리의 최소 값을 구합니다.

   4-1. x와 y의 값이 다르다면 이어질 수 있는 선임으로 vector를 하나 구현해 이들을 전부 집어넣습니다.

5. 큐와 값이 담긴 백터를 통해서 트리가 전부 이어질 수 있는지 확인합니다.

 

 

접근 방법 - 4번

 

저는 line_cost 라는 백터에 정보를 담았습니다. for문을 통해서 이 백터의 크기 만큼 반복합니다. 백터속 구조체에 담긴 시작점과 도착점을 Find() 함수를 통해서 어디까지 이어져있는지를 확인합니다. 서로 값이 다르다면, 이를 합쳐주고 cost값을 더해줍니다.  - Union() + Find() 함수

서로 값이 다르다면 갈 수 있다는 뜻이니 list 백터에 서로 입력해 줍니다. 방향이 없는 선임으로 양쪽에 전부 넣어주는게 중요합니다. 

 

접근 방법 - 5번

 

전부 list 백터에 입력이 되었다면 전부 이어져있는지 탐색을 합니다. 큐에 1의 값을 넣어준 뒤에 list[1]에 저장되어 있는 값들을 확인합니다.(list[1]에 값이 있다는 뜻은 1지점에서 갈 수 있는 곳이라는 것입니다) 이들을 전에 방문하지 않았다면, 큐에 이 값을 넣어주고 탐색을 해봅니다. 탐색이 전부 끝났다면 1~N까지 check배열이 true인지 확인합니다. 이중에 false값이 하나라도 있다면 탐색하지 못한 곳이니 false를 return합니다 - view() 함수

 

 

자세한 것은 코드를 참고해주세요!

 

#include <iostream>
#include <stdio.h>
#include <cstdio>
#include <algorithm>
#include <string>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
using namespace std;

int N, M, K;
typedef struct li {
    int start;
    int finish;
    int cost;
}li;
int cnt;
bool check[1001];
vector<li> line;
vector<li> line_cost;
vector<int> list[1001];
int connect[1011];


void get_rid_of(int x) {
    line_cost.clear();
    for (int i = 1; i < line.size(); i++) {
        line_cost.push_back(line[i]);
    }
    line.clear();
    for (int i = 0; i < line_cost.size(); i++) {
        line.push_back(line_cost[i]);
    }
}

int Find(int x) {
    if (connect[x] == x) return x;
    else return x = Find(connect[x]);
}

void Union(int x, int y) {
    int xx = Find(x);
    int yy = Find(y);
    connect[xx] = yy;
}

bool view() {
    queue<int> q;
    q.push(1);
    check[1] = true;
    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int i = 0; i < list[x].size(); i++) {
            int xx = list[x][i];
            if (xx <= N && !check[xx]) {
                check[xx] = true;
                q.push(xx);
            }
        }
    }
    for (int i = 1; i <= N; i++) {
        if (check[i] == false) return false;
    }
    return true;
}

void solve() {
    while (1) {
        int mini = 0;
        if (cnt == K) break;
        if(cnt > 0)get_rid_of(cnt);
        cnt++;
        for (int i = 1; i <= 1001; i++) {
            connect[i] = i;
        }
        memset(check, false, sizeof(check));

        for (int i = 1; i < 1001; i++) list[i].clear();
        for (int i = 0; i < line_cost.size(); i++) {
            int x = Find(line_cost[i].start);
            int y = Find(line_cost[i].finish);
            if (x != y) {
                Union(x, y);
                list[x].push_back(y);
                list[y].push_back(x);
                mini += line_cost[i].cost;
            }
        }
        if (view()) cout << mini << " ";
        else cout << "0 ";
    }
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M >> K;
    for (int i = 0; i < M; i++) {
        int x, y;
        cin >> x >> y;
        line.push_back({ x,y,i + 1 });
        line_cost.push_back({ x,y,i + 1 });
    }
    solve();
    return 0;
}

 

 

질문 및 조언 댓글 남겨주세요!