[백준 5567] 결혼식

🔗알고리즘 문제

아직 문제를 더 풀어봐야 되겠지만 그래프 탐색 문제도 꽤나 생각할 거리가 있어 재밌는거 같다. BFS와 DFS에 관해서는 추후에 정리해봐야겠다.

문제 분석

이 문제는 상근이가 알고 있는 친구들의 친구 관계가 주어질 때 상근이의 결혼식에 누구누구를 초대할지 알아야하는 문제이다.

이 때, 상근이는 자신의 친구와 자신의 친구의 친구까지만 결혼식에 초대하려한다.

발상 & 알고리즘 설계

서로서로 연결되있는 친구관계를 알고있기 때문에 그래프탐색으로 해결할 수 있을 것이라 생각하였다.

6
5

[1 2] | [1 3] | [3 4] | [2 3] | [4 5]

위에 테스트케이스를 시각적으로 표현한 그래프이다.

위 그래프에서 보이는 것처럼 해당 테스트케이스에서 상근이는 자신의 친구인 2, 3과 친구의 친구인 4 3명만을 초대하게 된다.

탐색시 친구에서 친구로 이동하며 완전탐색을 진행하게끔 BFS를 사용하여 해결하였다.

코드

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

using namespace std;

int main(){
    int n;
    int m;

    int answer = 0;

    vector<vector<int>> list;
    vector<int> check;
    queue<int> q;

    cin >> n >> m;
    list.resize(n + 1);
    check = vector<int>(n + 1, -1);

    for(int i = 0; i < m; i++){
        int cur;
        int next;

        cin >> cur >> next;

        list[cur].push_back(next);
        list[next].push_back(cur);
    }

    q.push(1);

    while(q.empty() == false){
        int node = q.front();
        q.pop();

        for(int i = 0; i < list[node].size(); i++){
            int next = list[node][i];

            if(next != 1 && check[next] == -1 && check[node] < 1){
                ++answer;
                check[next] = check[node] + 1;
                q.push(next);
            }
        }
    }

    cout << answer;
}