백준 5567 - 결혼식 - BFS

문제

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

풀이전략

1. 상근이의 친구와 친구의 친구까지만 초대하는것이다. 문제를 제대로 읽어야한다.
2. BFS로 문제를 해결하되, 상근이부터 시작하여 친구의 친구들 까지만 찾는 것이다. 몇번을 거쳐서 만들어 진건지에 대한 value값을 넣어 해결해준다.
3. 중복인 친구를 넣지 않기위해 체크배열을 만들어준다.

코드

#include<bits/stdc++.h>

using namespace std;

int n, m;
// 동기들의 친구관계를 저장할 2차원 벡터
vector<int> a[501];
// 중복을 막기위한 ch배열
bool ch[501];


int main(){
    ios_base::sync_with_stdio(false);
    // freopen("../input.txt","rt",stdin);

    cin >> n >> m;
    int ta, tb;
    for(int i=1; i<=m; i++){
        cin >> ta >> tb;
        a[ta].push_back(tb);
        a[tb].push_back(ta);
    }

    queue<pair<int, int> > q;
    ch[1] = true;
    // 상근이를 먼저 큐에 넣어줌
    q.push(make_pair(1,0));
    int cnt = 0;
    while(!q.empty()){
        int ret = q.front().first;
        int val = q.front().second;
        q.pop();   
        // 친구의 친구일 경우 더이상 큐에 추가하는 과정을 거치지 않는다.
        if(val == 2) continue;
        for(int i=0; i<a[ret].size(); i++){
        	// 중복되지 않는 선에서 친구를 추가해주는 과정.
            if(!ch[a[ret][i]]){
               ch[a[ret][i]] = true; 
               cnt++;
               q.push(make_pair(a[ret][i], val+1));
            }
        }
    }
    cout<<cnt<<endl;
    return 0;
}

소감

간단하게 pair 자료구조를 사용하여 해결하였다. 이 문제를 풀때 친구의 친구까지만 찾는다는 것을 제대로 인지하지 못하여 모든 친구들을 다 찾았었는데,,, 역시 문제를 제대로 읽고, 문제에서 준 input, output을 잘 분석하는것이 중요하다.