백준 10423 - 전기가 부족해(C++)

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

10423번: 전기가 부족해

MST 문제였습니다. Union() + Find()를 할 때 기존과 다르게 Union 부분에서 조건을 걸어줘야 했던 문제였습니다.

 

문제 조건

문제 예시

출력 예시

 

문제 접근 방법 

1. 발전소의 번호를 입력받을때, 배열을 하나 만들어서 해당 지점에 발전소가 있다는 것을 표시한다.

2. 간선들의 정보를 입력받고, 비용에 따라 오름차순으로 정렬한다.

3. 정렬한 간선들의 갯수만큼 for문을 반복한다.

4. 선들의 시작점과 도착점을 Find() 함수를 통해서 어디까지 연결되어 있는지 확인한다.

5. 서로 향하는 지점이 다르다면, Union() 함수를 통해서 조건에 따라 합쳐준다.

 

 

문제 접근 방법 - 2번

bool cmp(li a, li b) {
    if (a.cost < b.cost) return true;
    return false;
}

비용에 따라서 오름차순으로 정렬했습니다.

 

 문제 접근 방법 - 4번 + 5번

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

void Union(int x, int y, int c) {
    int xx = Find(x);
    int yy = Find(y);
    if (elec[xx] == 1 && elec[yy] == 1) {
        return;
    }
    else if (elec[xx] == 1 && elec[yy] == 0) {
        connect[yy] = xx;
        mini_cost += c;
    }
    else {
        connect[xx] = yy;
        mini_cost += c;
    }
}

Find() 함수를 통해서 각 지점이 어디에 연결되어 있는지를 확인했습니다. 저는 만약에 한 지점이 연결되어 있는 곳이 있다면 그곳을 무조건 발전소로 향하도록 만들었습니다.

 

Union() 함수는 선의 시작점과 도착점을 Find() 했는데 값이 다를 경우에 실행되도록 했습니다. elec[] 배열은 발전소가 설치되어 있는 위치를 알려주는 함수입니다. xx ,yy에 대해서 나올수 있는 경우를 3가지로 잡았습니다. 

1. 두 지점다 발전소가 있는 경우 -> 연결 안하면 됩니다.

2. 두 지점중 한 지점만 발전소가 있는 경우 -> 발전소가 있는 지점에다가 연결해줍니다.

 

 

 

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

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <queue>
#include <vector>
#include <stack>
#include <cmath>
using namespace std;

int N, num_line, K, mini_cost;
int connect[1001];
int elec[1001];
typedef struct li {
    int start;
    int finish;
    int cost;
}li;
vector<li> line;

bool cmp(li a, li b) {
    if (a.cost < b.cost) return true;
    return false;
}

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

void Union(int x, int y, int c) {
    int xx = Find(x);
    int yy = Find(y);
    if (elec[xx] == 1 && elec[yy] == 1) {
        return;
    }
    else if (elec[xx] == 1 && elec[yy] == 0) {
        connect[yy] = xx;
        mini_cost += c;
    }
    else {
        connect[xx] = yy;
        mini_cost += c;
    }
}

void solve() {
    sort(line.begin(), line.end(), cmp);
    for (int i = 0; i <= N; i++) {
        connect[i] = i;
    }
    for (int i = 0; i < line.size(); i++) {
        int x = Find(line[i].start);
        int y = Find(line[i].finish);
        if (x != y) {
            Union(x, y, line[i].cost);
        }
    }
    cout << mini_cost;
}

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

 

 

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