2606번 바이러스 | DFS 깊이우선탐색 | Baekjoon BOJ 백준 2606 C++ 코드, 해설, 풀이

 

 

 

이번 포스팅은 백준 2606번 바이러스입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/2606

2606번: 바이러스

 

 

 

기본 알고리즘

DFS 깊이 우선 탐색 사용

 

BFS 너비 우선 탐색 사용 가능

2021/01/27 - [[백준 알고리즘]] - 2606번 바이러스 | BFS 너비우선탐색 | Baekjoon 백준 2606 C++ 코드, 해설, 풀이

2606번 바이러스 | BFS 너비우선탐색 | Baekjoon 백준 2606 C++ 코드, 해설, 풀이

 

참고

line 10, 14
정점 방문하여 visited[v]=true로 갱신할 때마다 ans 1 증가시킴

line 34
1번 컴퓨터 제외 1번 컴퓨터와 연결된 컴퓨터 수 출력

 

 

 

전체 코드

 

//백준2606 바이러스
 
#include <iostream>
using namespace std;
 
int V, E;
const int MAX = 101;
int map[MAX][MAX] = { 0, };
bool visited[MAX] = { 0, };
int ans = 0;
 
void DFS(int v) {
    visited[v] = true;
    ans++;
 
    for (int i = 1; i <= V; i++) {
        if (visited[i]==0 && map[v][i] == 1) {
            DFS(i);
        }
    }
}
 
int main() {
    cin >> V >> E;
    for (int i = 0; i < E; i++) {
        int a, b;
        cin >> a >> b;
        map[a][b] = 1;
        map[b][a] = 1;
    }
 
    DFS(1);
    
    cout << ans - 1;
}