(C++) - 백준(BOJ) 5567번 : 결혼식

www.acmicpc.net/problem/5567

5567번: 결혼식

bfs를 이용하여 푼 문제였습니다.

 

풀이방법

 1. 입접행렬을 만들어줍니다.  a, b가 친구라면 b,a도 친구입니다. 양방향 그래프로 push_back으로 해야합니다.

 2. 상근이를 start node로 해 bfs를 시행합니다. visited배열을 선언합니다. 이는 i번째 노드의 level이 저장되어 있고 이는 방문했는지의 여부 또한 볼 수 있는 2가지의 용도입니다. 방문하지 않은 노드가 있으면 해당 노드를 방문 해주고 이전 노드의 level + 1을 저장해줍니다. 만약 이전 노드의 level이 2이하라면 정답을 더해줍니다. 

 3. 답을 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int n, m;
vector <int> graph[501];
int visited[501];
int bfs(int start){
    int ans = 0;
    queue <int> q;
    visited[start] = 1;
    q.push(start);
    while(!q.empty()){
        int x = q.front();
        q.pop();
        for(int i = 0; i < graph[x].size(); i++){
            if(visited[graph[x][i]]) continue;
            visited[graph[x][i]] = visited[x] + 1;
            if(visited[x]<=2) ans++;
            q.push(graph[x][i]);
        }
    }
    return ans;
}

int main(){
    cin >> n >> m;
    for(int i = 0; i < m; i++){
        int u,v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    cout << bfs(1);
}