5567번: 결혼식

[yeonddori]

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

문제 설명

상근이가 결혼식을 준비하며 친구 관계를 기반으로 초대할 사람의 수를 계산하는 문제입니다.
친구 관계는 무방향 그래프로 주어지며, 상근이와 친구, 그리고 친구의 친구까지만 초대할 수 있습니다. (친구의 친구의 친구는 초대 불가)

문제 풀이

BFS를 활용하여 상근이(1번 노드)부터 시작해 초대 가능한 사람을 탐색했습니다. 방문 여부를 기록하여 중복 초대를 방지하였으며, 친구의 친구까지만 초대할 수 있으므로 BFS 탐색 과정에서 현재 탐색 중인 노드가 상근이(1번 노드)일 경우에만 다음 노드를 큐에 추가하여 초대 인원을 세는 방식을 사용했습니다.

코드

#include <bits/stdc++.h>
using namespace std;

vector<vector<int>> friends;
vector<bool> visited;

int bfs() {
    queue<int> q;
    q.push(1);
    visited[1] = true;
    int cnt = 0;

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        for (int y : friends[x]) {
            if (!visited[y]) {
                if (x == 1) q.push(y);
                visited[y] = true;
                cnt++;
            }
        }
    }

    return cnt;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m;
    cin >> n >> m;
    friends.resize(n + 1);
    visited.resize(n + 1);

    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        friends[a].push_back(b);
        friends[b].push_back(a);
    }

    cout << bfs();

    return 0;
}

후기

처음에는 친구의 친구까지만 초대하는 방법이 쉽게 떠오르지 않아 한참을 고민했습니다. 깊이를 제한하기 위해 여러 방법을 시도했지만 번번이 실패했었죠.. 결국 마지막에 떠오른 방법이 이거였는데, 생각보다 간단해서 굉장히 허무했습니다!! ＼(´◓Д◔`)／