[MST] BOJ 16950 레드 블루 스패닝 트리 2

문제 링크 : www.acmicpc.net/problem/16950

16950번: 레드 블루 스패닝 트리 2

[먼저 풀면 좋은 문제]

[MST] BOJ 4792 레드 블루 스패닝 트리

 

레드 블루 스패닝 트리 문제를 실제로 구현해 보는 문제이다.

추가할 파란색 간선이 잇는 두 정점의 LCA를 구하는 과정에서 찾을 수 있는 아무 빨간색 간선을 없애고,

원래 추가하려 했던 파란색 간선을 잇는 과정을 파란색 간선의 개수가 k가 될 때까지 반복한다. 

문제에서 주어진 정점의 개수가 최대 1000개로 적은 편이기 때문에, 이 문제에서 LCA 알고리즘은 선형 시간에 구해도 무방하다.

 

단, 빨간색 간선 하나를 지우고 파란색 간선을 추가할 때마다 MST를 재구성 해주어야 한다.

다음과 같은 반례가 존재한다.

만약 3, 4번 정점을 잇는 파란색 간선을 추가한다고 가정해 보자.

3, 4번 정점의 LCA는 1번 정점으로, 이 과정에서 가장 먼저 만나는 2-3 빨간색 간선을 제거한 후 3-4 파란색 간선을 추가한다.

이제 스패닝 트리는 위와 같은 형태가 된다.

이 때, 각 정점의 Parent관계를 다시 재구성하지 않으면 3-5 파란색 간선을 추가하려 할 때

3, 5번 정점의 LCA가 4번 정점이 아닌 1번 정점이 되므로, 1-2 빨간색 간선이 지워지고 3-5 파란색 간선이 추가되어버린다. 물론 이는 스패닝 트리가 아니므로 오답이다.

 

실제 풀이 과정은 다음과 같다.

① 크루스칼 알고리즘을 통해, 최소의 파란색 간선을 갖는 MST를 구한다. 이 때 선택되는 간선들을 통해 MST에 대한 인접 리스트를 만든다. (코드의 mst vector)

② MST의 인접 리스트를 통해 DFS로 정점 간 Parent 관계를 설정한다. 이 때 사용되는 Parent 관계는 크루스칼 알고리즘의 Union-Find 알고리즘에서 사용되는 Parent와는 별개 정보이다. 

(코드에서 Union-Find 알고리즘의 parent는 ptemp로 선언되어 있다.)

③ 사용되지 않은 파란색 간선을 선택해, 그 간선이 잇는 두 정점에 대한 LCA를 구한다. 이를 구하는 과정에서 빨간색 간선을 발견했다면, 그것을 지우고 파란색 간선을 잇는다.

(코드에서는 conn이란 배열을 통해 연결 여부를 갱신하였으며, MST의 트리 관계 갱신을 위해 mst 인접 리스트에는 새로운 간선의 정보를 추가했다. LCA에서 체크할 때는 인접 리스트에 존재하더라도 conn 값이 false면 탐색하지 않는다.)

④ MST의 Parent 관계를 재구성한다. ③에서 갱신한 mst 및 conn 값들을 통해 DFS로 갱신하면 된다.

⑤ ③ ~ ④ 의 과정을 파란색 간선의 개수가 k가 될 때까지 반복한다.

 

[코드]

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>
#include <memory.h>
 
using namespace std;
typedef pair<int, int> p;
typedef pair<int, p> e;
 
int n, m, k, mst_cnt, blue_cnt;
vector<e> edges;
vector<p> blues;
vector<int> mst[1001];
int conn[1001][1001];
int ptemp[1001], parent[1001], level[1001];
 
int find_root(int x) {
    if (ptemp[x] == x) return x;
    return ptemp[x] = find_root(ptemp[x]);
}
 
void union_root(int x, int y) {
    x = find_root(x);
    y = find_root(y);
    if (x != y) ptemp[x] = y;
}
 
void kruskal() {
    for (int i = 0; i < edges.size(); i++) {
        e cur = edges[i];
        int f = cur.second.first, s = cur.second.second;
 
        if (mst_cnt == n - 1) {
            //쓰이지 않은 파란색 간선들을 따로 모아둔다.
            if (cur.first == 1) blues.push_back({ f, s });
            continue;
        }
 
        if (find_root(f) == find_root(s)) {
            if (cur.first == 1) blues.push_back({ f, s });
            continue;
        }
 
        union_root(f, s);
        if (cur.first == 1) blue_cnt++;
        mst[f].push_back(s);
        mst[s].push_back(f);
        conn[f][s] = cur.first;
        conn[s][f] = cur.first;
 
        mst_cnt++;
    }
}
 
void set_tree(int node, int pnode) {
    //mst를 구성
    parent[node] = pnode;
    level[node] = level[pnode] + 1;
 
    for (int i = 0; i < mst[node].size(); i++) {
        int child = mst[node][i];
        if (child == pnode) continue;
        if (conn[node][child] == -1 || conn[child][node] == -1) continue;
 
        set_tree(child, node);
    }
}
 
void substitute(p target) {
    //파란색 간선 target 을 MST에 추가하고, 붉은색 간선을 하나 뺀다.
    int f = target.first, s = target.second;
 
    //LCA를 통해 MST에서 두 노드 간 경로 중 붉은 간선을 찾는다.
    if (level[f] < level[s]) swap(f, s);
 
    while (level[f] != level[s]) {
        //f와 그 부모 노드의 간선 색을 확인
        if (conn[f][parent[f]] == 0 && conn[parent[f]][f] == 0) {
            //찾았다면, 그 간선을 MST에서 지우고 target을 추가
            conn[f][parent[f]] = -1;
            conn[parent[f]][f] = -1;
            conn[target.first][target.second] = 1;
            conn[target.second][target.first] = 1;
            mst[target.first].push_back(target.second);
            mst[target.second].push_back(target.first);
            blue_cnt++;
            return;
        }
        //찾지 못했다면 거슬러 올라감
        f = parent[f];
    }
 
    while (f != s) {
        //f와 그 부모 노드의 간선 색을 확인
        if (conn[f][parent[f]] == 0 && conn[parent[f]][f] == 0) {
            //찾았다면, 그 간선을 MST에서 지우고 target을 추가
            conn[f][parent[f]] = -1;
            conn[parent[f]][f] = -1;
            conn[target.first][target.second] = 1;
            conn[target.second][target.first] = 1;
            mst[target.first].push_back(target.second);
            mst[target.second].push_back(target.first);
            blue_cnt++;
            return;
        }
 
        //s와 그 부모 노드의 간선 색을 확인
        if (conn[s][parent[s]] == 0 && conn[parent[s]][s] == 0) {
            //찾았다면, 그 간선을 MST에서 지우고 target을 추가
            conn[s][parent[s]] = -1;
            conn[parent[s]][s] = -1;
            conn[target.first][target.second] = 1;
            conn[target.second][target.first] = 1;
            mst[target.first].push_back(target.second);
            mst[target.second].push_back(target.first);
            blue_cnt++;
            return;
        }
 
        f = parent[f];
        s = parent[s];
    }
}
 
void init() {
    int f, s, w;
    char type;
    cin >> n >> m >> k;
 
    for (int i = 1; i <= n; i++) ptemp[i] = i;
 
    for (int i = 0; i < m; i++) {
        cin >> type;
        cin >> f >> s;
        if (type == 'B') w = 1;
        else w = 0;
 
        edges.push_back({ w, {f, s} });
    }
 
    sort(edges.begin(), edges.end());
    memset(conn, -1, sizeof(conn));
}
 
void print_conn() {
    for (int i = 1; i <= n; i++) {
        for (int j = i + 1; j <= n; j++) {
            if (conn[i][j] != -1) printf("%d %d\n", i, j);
        }
    }
}
 
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(NULL);
 
    init();
    kruskal();
 
    if (mst_cnt < n - 1 || blue_cnt > k) {
        printf("0\n");
        return 0;
    }
 
    if (blue_cnt == k) {
        print_conn();
        return 0;
    }
 
    set_tree(1, 1);
 
    for (int i = 0; i < blues.size(); i++) {
        substitute(blues[i]);
        if (blue_cnt == k) {
            print_conn();
            return 0;
        }
        set_tree(1, 1);
    }
 
    printf("0\n");
 
    return 0;
}