[C++] 백준 2606번

바이러스 🦠

신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다. 예를 들어 7대의 컴퓨터가 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 이렇게 4대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다. 어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하쇼.

 

main.cpp

//
//  main.cpp
//  BFSnDFS
//
//  Created by Sun on 2023/04/08.
//

#include <iostream>
#include <vector>

int cntInfected = 0;

void dfs(int x, bool* vstd, std::vector<int>* graph) {
    vstd[x] = true;
    cntInfected++;      // 방문(처리)순서이자 감염순
    for (int i = 0; i < graph[x].size(); i++) {
        int y = graph[x][i];
        if (!vstd[y]) dfs(y, vstd, graph);    // 스택을 재귀로 구현!!
    }
}

int main() {
    
    int N, M;
    std::cin >> N >> M;
    
    bool visited[N+1];
    for (int i = 0; i < N+1; i++)   visited[i] = 0;
    std::vector<int> computer[N+1];
    
    for (int i = 0; i < M; i++) {   // 네트워크 연결 정보 저장
        int x, y;
        std::cin >> x >> y;
        computer[x].push_back(y);
        computer[y].push_back(x);
    }
    
    dfs(1, visited, computer);
    
    std::cout << cntInfected-1 << std::endl;    // 1번 컴퓨터는 카운트에서 제외
    
    return 0;
}

나는 전역변수를 쓰는게 먼가 마음에 안들어서 dfs의 파라미터를 늘리긴 했는데.... 머가 더 조흔건지는 아직 머르겟다 ㅜ 마찬가지로 인접리스트랑 행렬 중에 어떤거 쓰는게 좋은지도.... 머 장단점 알고 있으니 막힐 때만 바꿔도 되겠지...?

암튼 visited와 graph 배열에 대해서 전역변수로 만들어주고자 한다면 이 문제에서 주어지는 컴터 개수가 100개 이하라고 했으니까  bool visited[101] = {0,};이랑  vector<int> graph[101]; 정도로 선언하면 될 것 (특히 dfs/bfs 문제에서는 편의를 위해 노드 번호와 인덱스를 맞춰준당 그래서 +1 크기의 배열 사용 ㅋ)

bfs 풀이는 상상으로 대체하게씀.....