[백준] 5567 결혼식 구현

문제 :

https://www.acmicpc.net/problem/5567

5567번: 결혼식

 

분석 :

결혼식에 올 동기들 중 내 친구, 내 친구의 친구만 초대 하려면 몇명 초대 해야 묻는 문제였다.

친구 관계를 friends vector에 넣어 friends[친구] = ["친구의 친구들 리스트"] 를 찾으면 되는 문제지만 

 

* 주의 해야 할 점이 있다.

친구의 친구가 내 친구일 수도 있기 때문이다.

 

따라서 우선 내 친구들만 queue에 넣어 result 값을 증가시켜준 다음 queue에 있는 친구를 next로 찾아  

내 친구의 친구가 이미 내 친구인 경우 check 배열에서 true가 되었을 것이므로 if 문에 걸리지 않게 만들었다.

그래서 친구의 친구가 이미 내 친구로 main 함수에서 result 값이 증가 되었는데 find_real_friends에 중복되지 않게 해줬다 !

 

 

c++ 코드 :

//
//  5567_wedding.cpp
//  SOMA👩🏻‍💻
//
//  Created by JoSoJeong on 2021/05/07.
//

#include <stdio.h>
#include <iostream>
#include <vector>
#include <queue>
#include <string.h>

using namespace std;
int N;
int Tcase;
int result = 0;
vector<int> friends[501];
int check[501];
queue<pair<int, int>> q;

void find_real_friends(){
    while(!q.empty()){
        int next;
        if(q.front().first == 1){
            next = q.front().second; // 친구
        }else{
            next = q.front().first; // 친구
        }
      
        check[next] = true;
         
        for(int i = 0; i < friends[next].size(); i++){ // 친구의 친구
            if(check[friends[next][i]] == false){
                check[friends[next][i]] = true;
                result++;
            }
        }
        q.pop();
    }
}

int main(){
    cin >> N;
    cin >> Tcase;
    memset(check, false, sizeof(check));
    for(int i = 1; i <= Tcase; i++){
        int a, b;
        cin >> a >> b;
        if(a == 1 || b == 1){
            q.push({a, b}); // 내 친구들만 push
            check[a] = check[b] = true;
            result++;
        }
        
        friends[a].push_back(b);
        friends[b].push_back(a);
 
        
    }

    find_real_friends();
    cout << result << '\n';
    return 0;
}