[SW Expert] 5521. 상원이의 생일파티

링크

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AWWO3kT6F2oDFAV4&categoryId=AWWO3kT6F2oDFAV4&categoryType=CODE

SW Expert Academy

풀이

 

상원이가 친구들에게 줄 수 있는 초대장의 개수를 구하는 문제이다.

 

상원이가 초대장을 줄 수있는 경우는 친한친구와 친한친구의 친한친구 까지 줄수 있다.

 

이때 저는 친한 친구의 친한 친구를 어떻게 찾아야 될까 고민하다 dfs나 bfs를 이용하여 친구의 친구를 찾으면 되겠다 생각했습니다

 

그래서 친한 친구들을 인접리스트로 만든 후 

상원이부터 시작하여 친한친구의 친한 친구 까지 탐색을 하여 결과를 구했습니다.

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<cstring>
#include<functional>
#include<cmath>
#include<stack>

#define SIZE 555
const int INF = 2000000000;

using namespace std;

typedef long long int ll;
typedef pair<int, int> pii;

bool visited[SIZE];
void init() {
	for (int i = 0; i < SIZE; i++) {
		visited[i] = false;
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);

	int T; cin >> T;

	for(int t =1 ;t <=T;t++) {
		init();
		vector<int> arr[SIZE];
		queue < pair<int,int>> q;
		int N, M; cin >> N >> M;
		for (int i = 0; i < M; i++) {
			int a, b; cin >> a >> b;
			arr[a].push_back(b);
			arr[b].push_back(a);
		}

		int res = 0;
		q.push({ 1,0 });
		while (!q.empty()) {
			pair<int, int> h = q.front(); q.pop();

			visited[h.first] = true;
			if (h.second >= 2) {
				continue;
			}
			for (auto next : arr[h.first]) {
				if (visited[next] != true) {
					visited[next] = true;
					pair<int, int> n;
					n.first = next; n.second = h.second + 1;
					q.push(n);
					res++;
				}
			}
		}
		cout << '#' << t << " " << res << "\n";
	}
	
}