[구름 알고리즘 먼데이 챌린지] Week7 : 2. 퍼져나가는 소문

문제

"발 없는 말이 천 리 간다"는 옛말이 있듯, 한 번 퍼져나가기 시작한 소문은 막을 수 없이 퍼져나간다.

 

구름이는 N명의 친구가 있고, 그 친구들 중에는 M쌍의 친구 관계가 있다. 구름이가 만약 어떤 친구에게 소문을 퍼뜨리게 된다면, 그 소문은 친구의 친구, 친구의 친구의 친구... 를 타고 퍼져나갈 것이다.

 

구름이가 1번 친구에게 소문을 퍼뜨렸을 때, 그 소문을 듣게 될 친구가 몇 명이나 될지를 구해보자.

---

입력

첫 번째 줄에는 구름이의 친구의 수 N(1 <= N <= 500)이 주어진다. 모든 친구는 1번부터 N번까지 번호가 붙어 있다.

 

두 번째 줄에는 친구 관계의 수 M(1 <= M <= 1,000)이 주어진다. 

 

다음 M개의 줄에는 u, v(1 <= u, v <= N, u != v)가 공백으로 구분되어 주어진다. 모든 친구 관계는 양방향이고, 같은 친구 관계가 중복으로 주어지지 않는다.

 

입력에서 주어지는 모든 수는 정수이다.

---

간단한 그래프 탐색 문제로 판단하였고 DFS사용하여 문제를 해결하였다.

1번 노드를 시작으로 주어진 u,v 간선에 따라 끝까지 탐색하며 각 노드를 방문할 시 ans를 증가시켜주며 소문을 듣게 되는 친구의 수 ans를 구해주었다.

 

#include <iostream>
#include <vector>
using namespace std;

int n, m, u, v, ans;
vector<int> edge[501], visited(501);

void dfs(int cur) {
	visited[cur] = 1;
	ans++;
	int next;
	for (int i = 0; i < edge[cur].size(); i++) {
		next = edge[cur][i];
		if (visited[next]) continue;
		dfs(next);
	}
}

int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> u >> v;
		edge[u].push_back(v);
		edge[v].push_back(u);
	}
	dfs(1);
	cout << ans;
}