[C++] 백준 16562번 친구비

16562번: 친구비

그래프 탐색 문제.

그래프가 여러개 존재한다고 생각하고 각 그래프에서 최소값을 찾으면 되는 문제다.

 

문제풀이

각 친구마다 친구비가 드는데, 친구의 친구도 친구가 된다.

즉, 이는 친구 관계가 edge가 되고 학생은 vertex가 된다고 해석했다.

그 후, 연결된 Vertex들 끼리 그래프 탐색을 한 후에 최소비용을 찾으면 된다.

어차피 최소비용의 학생하고만 친구를 하면 나머지는 자동으로 친구가 될 수 있기 때문이다.

 

정답 코드

/*
* 백준 16562번 친구비
* https://www.acmicpc.net/problem/16562
* 그래프 탐색
*/
#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int studentCnt, friendCnt, money;
vector<vector<int>> adjFriendVec(10001);
int needMoney[10001];
bool visit[10001];
bool canAllFriend = true;
int ans = 0;

int findMinMoney(int startNum) {
    visit[startNum] = true;
    int minMoney = needMoney[startNum];
    queue<int> q;
    q.push(startNum);
    while (!q.empty()) {
        int num = q.front();
        q.pop();
        
        if (minMoney > needMoney[num]) {
            minMoney = needMoney[num];
        }

        for (int nxtNum : adjFriendVec[num]) {
            if (!visit[nxtNum]) {
                q.push(nxtNum);
                visit[nxtNum] = true;
            }
        }
    }
    return minMoney;
}

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

    cin >> studentCnt >> friendCnt >> money;

    int input;
    for (int i = 1; i <= studentCnt; i++) {
        cin >> input;
        needMoney[i] = input;
    }

    int f1, f2;
    for (int i = 0; i < friendCnt; i++) {
        cin >> f1 >> f2;
        adjFriendVec[f1].push_back(f2);
        adjFriendVec[f2].push_back(f1);
    }

    for (int i = 1; i <= studentCnt; i++) {
        if (!visit[i]) {
            int friendMinMoney = findMinMoney(i);

            if (friendMinMoney > money) { canAllFriend = false; break; }
            ans += friendMinMoney;
            money -= friendMinMoney;
        }
    }

    if (canAllFriend) {
        cout << ans;
    }
    else {
        cout << "Oh no";
    }

    return 0;
}

• 친구 관계를 2차원 벡터인 adjFriendVec에 저장해둔다.
  
  
• 각 학생마다 필요한 친구비용은 needMoney 배열에,
  해당 학생이 속한 그래프를 탐색했는지는 visit 배열에 기록해둔다.
  
  
• 만일 특정 그래프에서 최솟값을 지불하지 못할 경우에는
  canAllFriend를 false로 바꾼다.
  canAllFriend가 false라면 "Oh no"를 출력하고,
  true라면 ans를 출력한다.

그래프 탐색인 것을 알면 쉽게 해결할 수 있다.

 

GitHub - kimyunseok/cpp: C++로 코딩한 기록들을 담은 Repository입니다.

코드는 위에서 확인이 가능하다.