5567번 결혼식 | BFS | 백준 5567 C++ 코드

 

 

 

이번 포스팅은 백준 5567번 결혼식입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/5567

5567번: 결혼식

 

 

 

기본 알고리즘

BFS 너비 우선 탐색

 

 

 

전체 코드

 

//백준5567 결혼식                                                                    
 
#include <iostream>
using namespace std;
 
int n, m;
const int MAX = 501;
int map[MAX][MAX];
bool visited[MAX];
bool sFriend[MAX]; //상근이와 친구 여부
int ans = 0;
 
void count() {
    //상근이의 친구 
    for (int i = 2; i <= n; i++) {
        if (map[1][i] == 1) {
            visited[i] = true; //방문
            sFriend[i] = true; //상근이와 친구
        }
    }
    //상근이의 친구의 친구
    for (int i = 2; i <= n; i++) {
        if (sFriend[i]) { //상근이와 친구 
            for (int j = 1; j <= n; j++) {
                if (map[i][j]) { //친구의 친구
                    visited[j] = true; //방문
                }
            }
        }
    }
    //초대 인원 계산
    for (int i = 2; i <= n; i++) {
        if (visited[i]) {
            ans++;
        }
    }
}
 
int main() {
    cin >> n;
    cin >> m;
 
    while (m--) {
        int a, b;
        cin >> a >> b;
        map[a][b] = 1;
        map[b][a] = 1;
    }
 
    count();
    cout << ans;
}