백준 : 5567번 결혼식BFS(c++)

백준 링크

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

5567번: 결혼식

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
1 초	128 MB	16473	7251	5913	43.885%

문제

상근이는 자신의 결혼식에 학교 동기 중 자신의 친구와 친구의 친구를 초대하기로 했다. 상근이의 동기는 모두 N명이고, 이 학생들의 학번은 모두 1부터 N까지이다. 상근이의 학번은 1이다.

상근이는 동기들의 친구 관계를 모두 조사한 리스트를 가지고 있다. 이 리스트를 바탕으로 결혼식에 초대할 사람의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 상근이의 동기의 수 n (2 ≤ n ≤ 500)이 주어진다. 둘째 줄에는 리스트의 길이 m (1 ≤ m ≤ 10000)이 주어진다. 다음 줄부터 m개 줄에는 친구 관계 ai bi가 주어진다. (1 ≤ ai < bi ≤ n) ai와 bi가 친구라는 뜻이며, bi와 ai도 친구관계이다. 

출력

첫째 줄에 상근이의 결혼식에 초대하는 동기의 수를 출력한다.

예제 입력 1

6
5
1 2
1 3
3 4
2 3
4 5

예제 출력 1

3

예제 입력 2

6
5
2 3
3 4
4 5
5 6
2 5

예제 출력 2

0

코드 풀이

BFS탐색으로 풀이하였습니다.

처음에 DFS로 풀이하려다가 BFS가 올바른 풀이같다 생각이 들어 수정하였습니다.

상근이의 친구를 먼저 탐색하고 그친구의 친구까지 탐색을 해야하기 때문에 BFS 방식으로 구현하였습니다.

1. 먼저 입력된 값을 그래프에 연결

2. 학번과 깊이를 저장할 queue<pair<int, int>>를 선언 후 초기값 1, 0 저장(1은 상근이의 학번, 0은 처음 깊이)

3. 큐가 빌때까지 반복돌면서 방문하지 않은 노드를 큐에 저장 후 answer + 1;

코드

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <stack>

using namespace std;

int main()
{
    int N, M, Ai, Bi;

    cin >> N >> M;

    vector<vector<int>> Graph;
    Graph.resize(501);
    vector<bool> IsVisited(501);

    for (int i = 0; i < M; ++i)
    {
        cin >> Ai >> Bi;

        Graph[Ai].push_back(Bi);
        Graph[Bi].push_back(Ai);
    }

    queue<pair<int, int>> qPair;

    // 상근이의 학번인 1학번을 first로 넣어주고 Depth를 second로 넣어준다
    // Depth를 넣어주는 이유는 문제에서 친구와 친구의 친구까지만 초대가 가능하다고 되어있기 때문
    qPair.push({ 1, 0 });
    IsVisited[1] = true;

    int answer = 0;

    while (!qPair.empty())
    {
        int Cur = qPair.front().first;
        int Depth = qPair.front().second;
        qPair.pop();

        // Deapht가 2보다 작을때만 탐색
        if (Depth < 2)
        {
            for (int i = 0; i < Graph[Cur].size(); ++i)
            {
                if (!IsVisited[Graph[Cur][i]])
                {
                    IsVisited[Graph[Cur][i]] = true;
                    qPair.push({ Graph[Cur][i], Depth + 1 });
                    ++answer;
                }
            }
        }
    }

    cout << answer;

    return 0;
}