백준 14621 - 나만 안되는 연애(C++)

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

14621번: 나만 안되는 연애

문제 조건

 

출력 예시

쿠르스칼 알고리즘을 사용해서 풀었습니다.

 

문제 접근 방법

 

1. 각 학교가 남초 대학인지 여초대학인지 알 수 있는 배열을 선언해 값을 저장합니다.

2. 구조체 백터를 통해서 출발점, 도착점, 비용을 저장한뒤, 비용값에 따라 오름차순으로 정렬합니다.

3. 백터의 처음부터 마지막까지 for문을 돌립니다.

4. for문 안에서 출발점과 도착점이 서로 다른 성별인지를 확인합니다.

5. 다른 성별이라면 Find() 함수를 통해서 출발점에서 어디까지 갈 수 있는지 확인합니다.

6. 도착점도 같이 확인한후, 서로 갈 수 있는 곳이 다르다면, Union() 함수를 통해서 합쳐준뒤 비용을 더해줍니다.

7. MST를 끝낸후 후, 1번 점부터 시작해 끝까지 갈 수 있는지를 확인합니다.

 

 

문제 접근 방법 - 4번

    for (int i = 0; i < uni.size(); i++) {
        if (know_mf[uni[i].start] != know_mf[uni[i].finish]){
            int x = Find(uni[i].start);
            int y = Find(uni[i].finish);
            if (x != y) {
                Union(x, y);
                list[x].push_back(y);
                list[y].push_back(x);
                cnt_mini += uni[i].cost;
            }
        }
    }

배열의 칸에 해당 번호의 학교가 남초인지 여초인지 저장했습니다. 이를 먼저 비교해 서로 다른 성별이라면 정점들을 확인했습니다. 

 

 

문제 접근 방법 - 5번, 6번

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

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

Find(), Union() 함수를 통해서 각 정점이 어디까지 갈 수 있는지 확인하고 조건에 맞다면 합쳐줬습니다.

 

 

문제 접근 방법 - 7번

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

link_uni() 함수를 통해서 1번부터 N번까지 학교를 갈 수 있는 길이 있는지 살펴봤습니다. 

 

 

 

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

 

#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, M;
char know_mf[1001];
typedef struct li {
    int start;
    int finish;
    int cost;
}li;
vector<li> uni;
int connect[1001];
vector<int> list[1001];

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 xx = Find(x);
    int yy = Find(y);
    connect[xx] = yy;
}

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

void solve() {
    int cnt_mini = 0;
    for (int i = 0; i <= N; i++) {
        connect[i] = i;
    }
    for (int i = 0; i < uni.size(); i++) {
        if (know_mf[uni[i].start] != know_mf[uni[i].finish]){
            int x = Find(uni[i].start);
            int y = Find(uni[i].finish);
            if (x != y) {
                Union(x, y);
                list[x].push_back(y);
                list[y].push_back(x);
                cnt_mini += uni[i].cost;
            }
        }
    }
    if (link_uni(1)) cout << cnt_mini;
    else cout << "-1";
}

int main()
{
    cin.tie(0);
    cout.tie(0);
    cin >> N >> M;
    for (int i = 1; i <= N; i++) {
        cin >> know_mf[i];
    }
    for (int i = 0; i < M; i++) {
        int x, y, z;
        cin >> x >> y >> z;
        uni.push_back({ x,y,z });
    }
    sort(uni.begin(), uni.end(), cmp);
    solve();
    return 0;
}

 

 

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