5521. 상원이의 생일파티 (D5)

문제링크 : https://www.swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4&categoryId=AWWO3kT6F2oDFAV4&categoryType=CODE

< 입력 >

상원이의 같은 반 친구 수 (2<=N<=500)

친한 친구 관계 수(1<=M<=10^4)

< 출력 >

상원이가 초대장을 줘야 할 사람 수

< 풀이 >

조건이 있는 탐색 문제이다.

D5지만 크게 어려움은 없는 문제

문제를 간단하게 설명하면 상원이의 같은 반 친구들은 서로 친한 관계를 맺고 있는 사람이 있다.

상원이는 자신의 친한 친구들에게 먼저 초대장을 주고 다음으로 친한 친구의 친한 친구들에게 초대장을 주려고 한다.

즉, visited를 체크하며 depth 2의 사람까지 초대장을 주겠다는 뜻과 같다.

반 전체 인원은 최대 500명이므로 서로의 관계를 나타내기 위한 500*500의 자료구조가 필요하다.

다음으로 친구 관계를 입력받으며 서로의 인덱스에 체크를 해준다.

그렇게 받은 입력을 통해 상원 - 친구 - 친구 까지만 탐색을 하며 visited를 체크하고

count를 늘려주면 끝나는 문제이다.

---

- 소스 코드 -

#include<iostream>
#include<vector>
 
using namespace std;
 
int main(int argc, char** argv)
{
    int test_case;
    int T;
     
    cin>>T;
     
    for(int test_case=1;test_case<=T;test_case++){
        vector<int> arr[501];
        bool visited[501]={false};
        int N,M;
        cin>>N>>M;
        for(int i=0;i<M;i++){
            int a,b;
            scanf("%d %d",&a,&b);
            arr[a].push_back(b);
            arr[b].push_back(a);
        }
        vector<int> stack;
        stack.push_back(1);
        visited[1]=true;
        int result=0;
         
        while (!stack.empty()) {
            int cur = stack.back();
            stack.pop_back();
            for (int i = 0; i < arr[cur].size(); i++) {
                int k=arr[cur].at(i);
                if (!visited[k]) {
                    // cout<<k<<"한테 줄거얌"<<endl;
                    result++;
                    visited[k]=true;
                    if(cur==1){
                        stack.push_back(k);
                    }
                }
            }
        }
        printf("#%d %d\n",test_case,result);
 
    }
    return 0;//정상종료시 반드시 0을 리턴해야합니다.
}

---