[백준] 5567번 결혼식

 

 

문제

소스코드

 

#include<iostream>
#include<vector>
#include<queue>
#include<utility>
 
bool visited[501];
 
using Data = std::pair<int, int>; //Node, Depth
 
void BFS(std::vector<std::vector<int>>& list) {
 
    /*
    1번과의 길이를 2까지 허용하면 친구의 친구까지는 받을 수 있을듯
    */
 
    std::queue<Data> queue;
    int count{};
    //상근이 학번은 1번이기 때문에 1을 넣고 시작
    queue.emplace(1,0);
    visited[1] = true;
 
    while (queue.empty() == false) {
        auto frontValue = queue.front();
        queue.pop();
 
        for (auto& v : list[frontValue.first]) {
            //방문하지 않은 노드라면 넣고 탐색
            if (visited[v] == false) {
                visited[v] = true;
                queue.emplace(Data{ v,frontValue.second + 1 });
 
                if (frontValue.second < 2) {
                    ++count;
                }
            }
        }
    }
    std::cout << count << "\n";
}
 
int main() {
    int n, m;
    std::cin >> n >> m;
    std::vector<std::vector<int>>list(n + 1);
 
    for (int i = 0; i < m; ++i) {
        int me, other;
        std::cin >> me >> other;
        list[me].emplace_back(other);
        list[other].emplace_back(me);
    }
    BFS(list);
}

 

후기

 

이 문제를 해결하기 위한 키워드는 BFS이다.

 

예제에 있는 노드의 구성도는 다음과 같다 여기서 초대하는 친구는 2, 3, 4 (친구의 친구)까지만 허용한다는 점이 핵심이다.  나는 여기서 친구의 친구까지라는 깊이(2)를 제한으로 둬서 문제를 풀었다 

 

1부터 탐색을 진행하면서 깊이를 증가시키고 해당 하는 깊이보다 적은 노드라면 친구의 친구까지 이기 때문에 Count를 증가시키고 답을 출력한다.

 

 

마지막으로 관련글에 JOI 문제는 대회에서 사용했던 TC(Test Case)가 공개된다고 해서 해당 링크를 추가 기제한다.

 

 

 

출처 및 레퍼런스

문제 링크: www.acmicpc.net/problem/5567

 

관련 글

[자료구조 알고리즘/탐색 알고리즘(Search)] - [알고리즘] 너비 우선 탐색(Breadth First Search)

[온라인 코딩/탐색(Search)] - [백준] 1260번 DFS와 BFS

[온라인 코딩/탐색(Search)] - [프로그래머스] 네트워크

[온라인 코딩/탐색(Search)] - [백준] 2606번 바이러스

[온라인 코딩/탐색(Search)] - [프로그래머스] 경주로 건설

 

JOI: gooddaytocode.blogspot.kr/2016/12/japanese-olympiad-in-informatics-joi.html