#2606 바이러스

# 문제

# 입력 및 출력

# 풀이

BFS, DFS 둘 다 가능한 것 같아서 두가지 방법으로 풀어봄

1) BFS

// BFS
#include <iostream>
#include <queue>
using namespace std;
int connect[101][101];
int visit[101];
queue<int> q;

int main() {
	int n, m, s, e, cnt = 0;
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> s >> e;
		connect[s][e] = 1;
		connect[e][s] = 1;
	}
	q.push(1);
	visit[1] = 1;
	while (!q.empty()) {
		int t = q.front();
		for (int i = 1; i <= n; i++) {
			if (connect[t][i] && !visit[i]) {
				cnt++;
				q.push(i);
				visit[i] = 1;
			}
		}
		q.pop();
	}
	cout << cnt << "\n";
}

연결되어있는지 확인하는 배열인 connect를 단방향으로만 설정해줘서 한번 틀렸다

연결은 양방향이기 때문에 connect[s][e]와 connect[e][s] 둘 다 1로 설정해줘야 함

 

2) DFS

// DFS
#include <iostream>
using namespace std;
int n, m, s, e, cnt;
int connect[101][101];
int visit[101];

void dfs(int k) {
	for (int i = 1; i <= n; i++) {
		if (connect[k][i] && !visit[i]) {
			visit[i] = 1;
			cnt++;
			dfs(i);
		}
	}
}

int main() {
	cin >> n >> m;
	for (int i = 0; i < m; i++) {
		cin >> s >> e;
		connect[s][e] = 1;
		connect[e][s] = 1;
	}
	visit[1] = 1;
	dfs(1);
	cout << cnt << "\n";
}

DFS가 더 보기 편한듯ㅋㅋ

 

아직 bfs, dfs가 익숙하지가 않아서 기억 안날때마다 슈도코드 보고 구현하는데

많이 풀어봐야 익숙해져서 금방금방 쓸듯

그리디랑 dp문제만 풀지말고 그래프도 많이 풀기,,ㅋㅋ