[백준/c++] 2606번: 바이러스

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

2606번: 바이러스

 

문제 요약

 

1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하라.

 

범위

 

컴퓨터의 수 100 이하

 

 

---

 

 

 

어떤 그래프 탐색을 선택해야 더 효율적인 방법인지 생각해봤다.

DFS는 깊이 우선 탐색으로 원하는 값을 찾을 때까지 깊게 들어간다. 현 경로상의 데이터만 기억하면 되므로 저장 공간을 적게 사용한다. 얻은 해가 최단 경로를 보장하지 않는다. (→ 최단 경로를 찾는 방법은 BFS에 더 적절하다)

BFS는 모든 노드를 탐색하는 너비 우선 탐색으로 더 이상 방문할 수 없는 노드가 없을 때까지 모든 노드를 탐색하는 것으로 최단 경로를 찾는 방법으로 적절하다. 경로가 길어지면 많은 기억 공간이 필요하고, 출발 노드에서 목표 노드까지의 최단 길이를 보장할 수 있다.

 

더 이상 방문할 수 없는 노드가 없을 때까지 == 바이러스에 걸리지 않은 컴퓨터가 없을 때까지 라고 생각했는데, 최단 경로를 찾는 문제도 아니고 모든 노드를 탐색하는 것이므로 DFS가 더 적절할 수 있다고 생각했다. 

 

둘 다 해보자.

과연 어떤 방법이 더 적절할까?

 

//BFS
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
int n, p, a, b;
vector<int> graph[101];
bool visited[101] = {false};

void input(){
    cin >> n >> p;
    for(int i=0; i<p; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void bfs(){
    int st = 1, cnt = -1;
    queue<int> q;
    q.push(st);
    visited[st] = true;
    while(!q.empty()){
        int x = q.front();
        q.pop();
        cnt++;
        for(int i=0; i<graph[x].size(); i++){
            int y = graph[x][i];
            if(!visited[y]){
                q.push(y);
                visited[y] = true;
            }
        }
    }
    cout << cnt << '\n';
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    bfs();
    return 0;
}

 

//DFS
#include <iostream>
#include <vector>
using namespace std;
int n, p, a, b, cnt=-1;
vector<int> graph[101];
bool visited[101] = {false};

void input(){
    cin >> n >> p;
    for(int i=0; i<p; i++){
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
}

void dfs(int x){
    cnt++;
    visited[x] = true;
    for(int i=0; i<graph[x].size(); i++){
        int y = graph[x][i];
        if(!visited[y]) dfs(y);
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    input();
    dfs(1);
    cout << cnt << '\n';
    return 0;
}

 

 

 

걸리는 시간이 비슷하지만 메모리 부분에서 DFS가 더 효과적인 것이 보인다. 사실 그렇게 차이가 나지 않다ㅋㅋ

다음에 문제를 풀 때는 저장공간에 있어서 더 효과적인 방법을 사용하도록 해야겠다~ 

 

 

 

 

 

💡공부 및 기록용 블로그이므로 오류가 있을 수 있습니다.💡

만약 문제에 오류나 오타가 있다면 댓글로 알려주세요➿
언제나 환영합니다. 감사합니다. 화이팅!