[백준] 5567 결혼식

5567번: 결혼식

 

www.acmicpc.net

풀이

상근이의 번호가 1번이므로 1번에서 시작해서 BFS로 친구의 친구까지 확인해주면 된다.

코드

C++

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int n, m;
vector<vector<int>> adj;

int bfs() {
    queue<int> q;
    vector<bool> visit(n + 1, false);
    q.push(1);
    visit[1] = true;

    int answer = 0;
    int count = 0;

    while (!q.empty()) {
        int size = q.size();

        if (count == 2) break;

        while (size--) {
            int current = q.front();
            q.pop();

            for (int i : adj[current]) {                
                if (!visit[i]) {
                    visit[i] = true;
                    q.push(i);
                    answer++;
                }
            }
        }
        count++;
    }
    return answer;
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;
    cin >> m;

    adj = vector<vector<int>>(n + 1);
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }    
    cout << bfs() << '\n';
    return 0;
}

Python3

import sys
from collections import deque

n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
adj = [[] for _ in range(n + 1)]

for _ in range(m):
    a, b = map(int, sys.stdin.readline().rstrip().split())
    adj[a].append(b)
    adj[b].append(a)


def bfs():
    q = deque([1])
    visit = [False] * (n + 1)
    visit[1] = True

    answer = 0
    count = 0
    while q:
        size = len(q)
        if count == 2:
            break

        while size:
            current = q.popleft()

            for i in adj[current]:
                if not visit[i]:
                    visit[i] = True
                    q.append(i)
                    answer += 1
            size -= 1
        count += 1
    return answer


print(bfs())