백준 5567 - 결혼식(C++)

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

5567번: 결혼식

그래프탐색을 이용해 푸는 문제입니다.

저는 BFS를 이용해 풀었습니다.

 

자신의 친구와 친구의 친구를 결혼식에 초대하려고 할 때, 부를 수 있는 사람 수를 구하는 문제입니다.

친구의 친구까지 부를 수 있으니, 2번까지 이동할 수 있습니다.

 

1번 정점에서 시작해 2번까지 이동해서 자신과 연결된 정점 갯수를 찾아주면 됩니다.

 

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

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#include <cmath>
#define P pair<int, int>
#define F first
#define S second
using namespace std;

int N, M;
vector<int> connect[501];
int check[501];

int bfs(){
    int fre = 0;
    queue<P> q;
    check[1] = 1;
    q.push({1, 0});
    while(!q.empty()){
        int x = q.front().F;
        int cnt = q.front().S;
        q.pop();
        for(int i = 0; i < connect[x].size(); i++){
            int xx = connect[x][i];
            if(check[xx] == 1) continue;
            if(cnt + 1 >= 3) continue;
            check[xx] = 1;
            q.push({xx, cnt + 1});
            fre++;
        }
    }
    return fre;
}

void solve(){
    cout << bfs();
}

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

 

 

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