[백준(BOJ)] 2606번: 바이러스 (DFS/BFS, C++)

💻 C++ 코드 (제출 코드)

---

#include <stdio.h>
#include <vector>

using namespace std;

void dfs(int computer, vector<int> *graph, bool *check, vector<int> *worm){

    check[computer]=true; //방문 체크
    
    for(int i = 0; i < graph[computer].size(); i++){ //감염된 컴퓨터와 연결된 컴퓨터도 감염이므로 
        int next = graph[computer][i];
        if(check[next] == false){
            (*worm).push_back(next); //0포함 안되도록..
            dfs(next, graph, check, worm);
            
        }
    }
}

int main()
{
    int n,m; //n: 정점의 수, m: 간선의 수
   
    
    scanf("%d", &n);
    scanf("%d", &m);
    
    vector<int> graph[n];
    vector<int> worm_computer;
    bool check[n];
    
    fill(check, check+n, false);

    for(int i=0; i<m; i++)
    {
        int u,v; //네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍
        
        scanf("%d %d", &u, &v);
        //양방향 그래프
        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }
    
    dfs(0, graph, check, &worm_computer);

    printf("%d", worm_computer.size());

}

 

 

📝 문제풀이 과정

---

1. 그래프 만들기

• 정점의 개수(n)만큼 크기를 가지는 vector 리스트를 생성한다. 

  • 필자의 경우, 1번 컴퓨터가 0번째부터 들어가도록 만들었다.

• graph[i]는 i번째 정점에 연결된 정점들이 담긴다.

• 양방향 그래프이므로, 네트워크 상 직접 연결되어 있는 컴퓨터의 번호 쌍에 따라 vector에 값을 넣어줄 때 (u,v) 정점에 대해 graph[u-1]에 넣어주고, graph[v-1]에도 넣어준다.

2. 웜 바이러스 걸린 컴퓨터 구하기: DFS로 구현

• DFS 탐색을 재귀함수로 구현해서, 각 컴퓨터에 연결된 컴퓨터에 연결된 모든 컴퓨터가 고려되도록 한다.

• 먼저 visited로 탐색 유무를 판단한다. 양방향 그래프이기 때문에 이미 방문한 컴퓨터를 다시 탐색할 가능성이 존재하기 때문이다. 

• 함수 처음에 visited를 true로 하고, 해당 컴퓨터에 연결된 원소들에 대해 다음 탐색할 컴퓨터를 next로 가지고 만약 check[next]가 false이면 방문하지 않은 컴퓨터이므로 탐색한다. 

• dfs 함수 초반에 vector에 넣는 작업을 하면 맨 처음에 방문하는 1번 컴퓨터가 vector에 포함되게 되므로,  방문하지 않은 컴퓨터인 조건일 때에 vector에 넣어준다.

#include <stdio.h>
#include <vector>

using namespace std;


void dfs(int computer, vector<int> *graph, bool *check, vector<int> *worm){

    check[computer]=true; //방문 체크
    //(*worm).push_back(computer); //감염된 컴퓨터 vector에 넣음
    printf("[+] %d INFECTED\n", computer);
    for(int i = 0; i < graph[computer].size(); i++){ //감염된 컴퓨터와 연결된 컴퓨터도 감염이므로 
        int next = graph[computer][i];
        if(check[next] == false){
            (*worm).push_back(next); //1번 컴퓨터 포함 안되도록..
            dfs(next, graph, check, worm);
            
        }
    }
}

int main()
{
    int n,m; //n: 정점의 수, m: 간선의 수
   
    
    scanf("%d", &n);
    scanf("%d", &m);
    
    vector<int> graph[n];
    vector<int> worm_computer;
    bool check[n];
    
    fill(check, check+n, false);

    for(int i=0; i<m; i++)
    {
        int u,v; //네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍
        
        scanf("%d %d", &u, &v);
        //양방향 그래프
        graph[u-1].push_back(v-1);
        graph[v-1].push_back(u-1);
    }
    
    dfs(0, graph, check, &worm_computer); //1번 컴퓨터부터 방문 시작


    printf("\ninfected computers: ");
    for(int c: worm_computer) printf("%d ", c);
    printf("\n# of infected: %d", worm_computer.size());

}

 

 

 

🙄 반례

---

5 
4 
1 3 
1 4 
2 5 
3 2

• 문제를 풀 때 생각하지 못한 반례는 위와 같다.

 

 

 

👏 결과

---