백준 2606 : 바이러스

https://www.acmicpc.net/problem/2606

간단하다. BFS로 풀어도 되고 DFS 로 풀어도 되고 심지어 플로이드-와샬을 써도 된다.

그냥 단순히 그래프의 연결문제를 탐색하는 것.

숫자만 세는 것이므로

BFS 나 DFS로 visited = true; 라고 새롭게 방문을 하는 순간

count++ 해주면 된다.

1. 큐를 이용한 BFS

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

#include <iostream> #include <queue> #define MAX 101 using namespace std; int matrix[MAX][MAX]; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; while(m--){ int a, b; cin >> a >> b; matrix[a][b] = 1; matrix[b][a] = 1; } int count = 0; queue<int> q; q.push(1); visited[1] = true; while(!q.empty()){ int cur = q.front(); q.pop(); for(int i = 1; i <= n; i++){ if(matrix[cur][i] == 1 && !visited[i]){ visited[i] = true; q.push(i); count++; } } } cout << count << '\n'; return 0; }

2. 스택을 이용한 DFS

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include <iostream> #include <stack> #define MAX 101 using namespace std; int matrix[MAX][MAX]; bool visited[MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; while(m--){ int a, b; cin >> a >> b; matrix[a][b] = 1; matrix[b][a] = 1; } int count = 0; stack<int> st; st.push(1); visited[1] = true; while(!st.empty()){ int cur = st.top(); bool flag = true; for(int i = 1; i <= n; i++){ if(matrix[cur][i] == 1 && !visited[i]){ visited[i] = true; st.push(i); flag = false; count++; break; } } if(flag) st.pop(); } cout << count << '\n'; return 0; }

3. 플로이드-와샬

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41

#include <iostream> #define MAX 101 #define INF 987654321 using namespace std; int matrix[MAX][MAX]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); int n, m; cin >> n >> m; for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ matrix[i][j] = (i==j) ? 0:INF; } } while(m--){ int a, b; cin >> a >> b; matrix[a][b] = 1; matrix[b][a] = 1; } for(int k = 1; k <= n; k++){ for(int i = 1; i <= n; i++){ for(int j = 1; j <= n; j++){ if(matrix[i][j] > matrix[i][k] + matrix[k][j]){ matrix[i][j] = matrix[i][k] + matrix[k][j]; } } } } int count = 0; for(int i = 1; i <= n; i++){ if(matrix[1][i] != INF && matrix[1][i] != 0) count++; } cout << count << '\n'; return 0; }