[BOJ] 5567 결혼식

cjeongmin·2일 전
0

문제


문제링크



풀이

그래프 탐색에 관한 문제인데 BFS를 이용했다.
queue에 현재 depth를 같이 저장하면서 depth가 2이면 그 이후는 친구의 친구를 벗어나기에 더 이상 탐색하지 않는 방식으로 해결했다.


소스 코드

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

using namespace std;

int main() {
    int n, m, a, b, ans = 0;
    cin >> n >> m;
    vector<vector<int>> graph(n + 1, vector<int>());

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

    queue<pair<int, int>> q;
    vector<bool> visit(n + 1);
    visit[1] = 1;
    q.push({1, 0});

    while (!q.empty()) {
        auto curr = q.front();
        q.pop();

        if (curr.second == 2)
            continue;

        for (int i = 0; i < graph[curr.first].size(); i++) {
            int next = graph[curr.first][i];
            if (visit[next]) continue;
            visit[next] = 1;
            q.push({next, curr.second + 1});
            ans++;
        }
    }

    cout << ans << "\n";
    return 0;
}

0개의 댓글