[백준] 4792번 : 레드 블루 스패닝 트리 - C++ / JAVA

백준 4792 : 레드 블루 스패닝 트리

등급 : Platinum III

4792번: 레드 블루 스패닝 트리 (acmicpc.net)

4792번: 레드 블루 스패닝 트리

사용 알고리즘 : Kruskal Algorithm

사용 자료구조 : Vector, Union-Find

 

크루스칼 알고리즘을 두 번 이용하여 스패닝 트리의 수정 가능성을 확인하는 문제였습니다.

위의 그래프를 예로 들어보자.

먼저 파란색 간선을 최소로 사용해주기 위해 빨간색으로 이뤄진 간선을 모두 이어준다.

이후 각 정점을 확인하며 연결을 하게 되면 위와 같은 스패닝 트리가 나타나게 된다.

이 때가 파란색 간선을 가장 적게 사용하는 경우이므로, 최솟값은 3이 된다.

 

두 번째로, 파란색 간선을 가장 많이 사용하는 경우를 보기 위해 파란색 간선으로만 스패닝 트리를 생성해본다.

이 때가 파란색 간선을 가장 많이 사용하는 경우이므로 최댓값은 5가 된다.

 ( 두 번째 단계를 진행할 때, 파란 간선을 모두 연결해도 스패닝 트리가 되지 않아도 상관 없다. )

 

이후 목표값이 이 범위 사이에 있다면 1, 그렇지 않다면 0을 출력해준다.

 ( 빨간 색 간선으로 바꿔주며 이 범위 내에 있는 파란 색 간선을 모두 표현할 수 있기 때문 )

cpp

코드 펼치기 줄바꿈

#include <iostream>
#include <vector>

using namespace std;

int n, m, k;
int par[1001];
vector <pair <int, int>> v_r;
vector <pair <int, int>> v_b;

void init(int n)
{
    for (int i = 1; i <= n; i++)
    {
        par[i] = i;
    }
}

int find(int x)
{
    if (x == par[x]) return x;
    else return par[x] = find(par[x]);
}

bool uni(int x, int y)
{
    x = find(x);
    y = find(y);
    if (x == y) return false;
    else
    {
        par[x] = par[y] = min(x, y);
        return true;
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int x, y, mini, maxi;
    string col;
    while (1)
    {
        cin >> n >> m >> k;
        if (n == 0 && m == 0 && k == 0) break;
        mini = 0;
        maxi = 0;
        v_r.clear();
        v_b.clear();
        init(n);
        for (int i = 0; i < m; i++)
        {
            cin >> col >> x >> y;
            if (col == "R") v_r.push_back({ x, y });
            else v_b.push_back({ x, y });
        }
        for (int i = 0; i < v_r.size(); i++)
        {
            uni(v_r[i].first, v_r[i].second);
        }
        for (int i = 0; i < v_b.size(); i++)
        {
            bool chk = uni(v_b[i].first, v_b[i].second);
            if (chk) mini++;
        }
        init(n);
        for (int i = 0; i < v_b.size(); i++)
        {
            if (uni(v_b[i].first, v_b[i].second)) maxi++;
        }

        if (mini <= k && k <= maxi) cout << 1 << "\n";
        else cout << 0 << "\n";
    }
}

java

코드 펼치기 줄바꿈

import java.util.*;
import java.io.*;

public class Main{
    static List<int[]> v_r = new ArrayList<>();
    static List<int[]> v_b = new ArrayList<>();
    static int[] par = new int[1001];

    static void initPar(int n)
    {
        for(int i=1; i<=n; i++)
        {
            par[i] = i;
        }
    }
    static int find(int x)
    {
        if(x == par[x]) return x;
        else return par[x] = find(par[x]);
    }
    static boolean uni(int x, int y)
    {
        x = find(x);
        y = find(y);
        if(x == y) return false;
        else
        {
            par[x] = par[y] = Math.min(x, y);
            return true;
        }
    }
    static public void main(String[] agrs) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader (System.in));
        StringTokenizer st;
        StringBuilder sb = new StringBuilder();
        int n, m, k, mini, maxi;
        
        while(true)
        {

            st = new StringTokenizer(br.readLine());
            n = Integer.parseInt(st.nextToken());
            m = Integer.parseInt(st.nextToken());
            k = Integer.parseInt(st.nextToken());
            if(n == 0 && m == 0 && k == 0) break;
            mini = 0;
            maxi = 0;
            for(int i=0; i<m; i++)
            {
                st = new StringTokenizer(br.readLine());
                if(st.nextToken().equals("B"))
                {
                    int[] arr = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
                    v_b.add(arr);
                }
                else
                {
                    int[] arr = {Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken())};
                    v_r.add(arr);
                }

            }
            initPar(n);
            for(int i=0; i<v_r.size(); i++)
            {
                uni(v_r.get(i)[0], v_r.get(i)[1]);
            }
            for(int i=0; i<v_b.size(); i++)
            {
                if(uni(v_b.get(i)[0], v_b.get(i)[1])) mini++;
            }
            initPar(n);
            for(int i=0; i<v_b.size(); i++)
            {
                if(uni(v_b.get(i)[0], v_b.get(i)[1])) maxi++;
            }
            if(mini <= k && k <= maxi) sb.append(1).append("\n");
            else sb.append(0).append("\n");
            v_r.clear();
            v_b.clear();
        }
        System.out.println(sb);
    }
}