[BFS] 백준 5567번 결혼식

백준 5567번

결혼식

BFS를 이용하는 전형적인 문제이지만 한 가지 제한 사항이 있다. 친구의 친구까지만 제한을 하는 방식이다.

예전에는 상근이의 직속 친구들을 따로 분류하고 그 친구들의 친구를 세는 방법을 생각했었는데, 잘 되지 않았던 것으로 기억한다.

이번에는 BFS로 접근하되 level 을 나타내는 배열을 추가로 생성하여 첫 시작인 상근이가 0, 이후 추가되는 친구들은 자신을 초대한 사람의 level보다 1 높은 level을 가지게 하여 상근이(0), 상근이의 친구(1), 상근이의 친구의 친구(2), 즉 level 2까지만 초대하게 하였다.

BFS문제를 풀 때 생각보다 구조체 등을 이용하면 헷갈리지 않고 편하게 문제를 풀 수 있었다.

다만 메모리 적인 측면이나 다른 관점에서 구조체를 사용함으로써 발생하는 문제가 있지는 않은지 살펴봐야겠다.

추가적으로, 문제에서 친구 관계가 양방향임을 명시하고 있기 때문에 입력을 받을 때 고려하여야 한다 .

구조체를 이용한 풀이

#include <iostream>
#include <queue>
#include <vector>

using namespace std;

struct friends{
    bool invited;
    vector<int> status;
    int level; 
};

int main(){
    int friends, relation_num;
    cin >> friends >> relation_num;
    vector<struct friends> relations;
    for(int i=0;i<=friends;i++){
        struct friends tmp;
        tmp.invited = false;
        tmp.level = -1;
        relations.push_back(tmp);
    }
    for(int i=0;i<relation_num;i++){
        int person1,person2;
        cin >> person1 >> person2;
        relations[person1].status.push_back(person2);
        relations[person2].status.push_back(person1);
    }
    queue<int> q;
    q.push(1);
    relations[1].invited=true;
    relations[1].level=0;
    int count = 0;
    while(!q.empty()){
        int front = q.front();
        q.pop();

        for(int i=0;i<relations[front].status.size();i++){
            if(!relations[relations[front].status[i]].invited && relations[front].level <=1){
                q.push(relations[front].status[i]);
                relations[relations[front].status[i]].level = relations[front].level + 1;
                relations[relations[front].status[i]].invited = true;
                count ++;
            }

        }
    }
    cout << count << endl;
}

배열을 사용한 풀이

#include <iostream>
#include <queue>
#include <vector>

using  namespace std;

int main(){
    int num1, num2; cin >> num1 >> num2;
    vector<int> relations[501];
    vector<bool> invited(501,false);
    vector<int> level(501,-1);
    for(int i=0;i<num2;i++){
        int tmp1, tmp2;cin>>tmp1>>tmp2;
        relations[tmp1].push_back(tmp2);
        relations[tmp2].push_back(tmp1);
    }
    queue<int> q; q.push(1); invited[1]=true; level[1]=0;
    int answer = 0;
    while(!q.empty()){
        int cur = q.front(); q.pop();
        for(int i=0;i<relations[cur].size();i++){
            int friends = relations[cur][i];
            if(!invited[friends]&&level[cur]<=1){
                q.push(friends);
                invited[friends] = true;
                level[friends]=level[cur]+1;
                answer++;
            }
        }
    }        
        cout << answer << endl;
}