[BFS] 결혼식 (백준 5567번)

 

상근이는 1번을 학번으로 가지고 있다.

또한 상근이를 포함해 n번까지의 학생이 있고,

우리는 그 인간관계 m개를 받아서 서로의 친구 관계에 대해서 파악해볼 것이다.

 

만약 1번과 2번이 친구고, 2번과 3번이 친구라면 1번과 3번 역시 자동으로 친구다.

한 마디로 같이 노는 그룹 전체를 친구라고 한다는 것이다. (가운데 한 명 빠지면 어색해지는 사이라고 해도.)

 

나는 이것을 bfs 방식으로 풀었다.

bfs의 매개변수에 상근이의 학번을 전달한 다음에, 방문 여부를 모두 체크해서,

방문할 수 있었던 모든 학번에 대하여 친구라고 가정하여 출력한다.

 

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
vector<int> map[1001];
 
int n, m;
int visited[1001];
 
void bfs(int start)
{
    int counted = 0;
    visited[start] = 1;
    queue<int> Q;
    Q.push(start);
 
    while (!Q.empty())
    {
        counted++;
        int current = Q.size();
 
        for (int i = 0; i < current; i++)
        {
            int cur = Q.front();
            Q.pop();
 
            for (int j = 0; j < map[cur].size(); j++)
            {
                int next = map[cur][j];
 
                if (visited[next] == 0
                    && counted <= 2)
                {
                    visited[next] = 1;
                    Q.push(next);
                }
            }
        }
    }
}
 
int main(void)
{
    cin >> n >> m;
    for (int i = 0; i < m; i++)
    {
        int from, to;
        cin >> from >> to;
 
        map[from].push_back(to);
        map[to].push_back(from);
    }
 
    bfs(1);
 
    int sum = 0;
    for (int i = 1; i <= n; i++)
    {
        sum += visited[i];
    }
    cout << sum - 1;
}