바이러스 (feat. 백준, 2606번)

바이러스
https://www.acmicpc.net/problem/2606

2606번: 바이러스

 

반응형

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
using namespace std;
int N, M;
bool check[101][101];
bool visit[101];
void dfs(int n) {
	visit[n] = true;
	for (register int i = 1; i <= N; ++i)
		if (check[n][i] && !visit[i])
			dfs(i);
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> M;
	for (register int i = 1, j; i <= N; ++i) {
		visit[i] = false;
		for (j = 1; j <= N; ++j)
			check[i][j] = false;
	}
	for (register int m = 0, x, y; m < M; ++m)
		cin >> x >> y, check[x][y] = check[y][x] = true;
	dfs(1);
	register int ans = 0;
	for (register int i = 2; i <= N; ++i)
		if (visit[i])
			++ans;
	cout << ans;
	return 0;
}
// *&)*@*

DFS를 통한 풀이

 

// woohyeon.kim
// kim519620.tistory.com
#include <iostream>
#include <queue>
using namespace std;
int N, M;
bool check[101][101];
bool visit[101];
void bfs(int n) {
	visit[n] = true;
	queue<int> q;
	q.push(n);
	while (!q.empty()) {
		auto v = q.front(); q.pop();
		for (register int i = 1; i <= N; ++i)
			if (check[v][i] && !visit[i])
				visit[i] = true, q.push(i);
	}
}
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	cin >> N >> M;
	for (register int i = 1, j; i <= N; ++i) {
		visit[i] = false;
		for (j = 1; j <= N; ++j)
			check[i][j] = false;
	}
	for (register int m = 0, x, y; m < M; ++m)
		cin >> x >> y, check[x][y] = check[y][x] = true;
	bfs(1);
	register int ans = 0;
	for (register int i = 2; i <= N; ++i)
		if (visit[i])
			++ans;
	cout << ans;
	return 0;
}
// *&)*@*

BFS를 통한 풀이

 

1. 연결된 노드의 개수를 구하는 문제이므로 DFS, BFS 모두 풀이가 가능합니다.
2. 1과 연결된 노드에 대해서 true로 마킹을 해두고 다음번 탐색때 마킹된 항목은 건너띄는 형태입니다.