백준 2606번 [바이러스](C++) -yes6686- 티스토리

백준 문제 풀이: 2606 [바이러스]

---

문제 링크: https://www.acmicpc.net/problem/2606

문제 설명:

네트워크 상에서 1번 컴퓨터가 바이러스에 감염되었을 때, 1번 컴퓨터로부터 바이러스가 전파될 수 있는 컴퓨터의 수를 구하는 문제입니다. 컴퓨터들은 양방향 연결이 가능하며, 연결 정보를 통해 감염 전파를 추적해야 합니다.

---

문제 해결 코드

// 백준 2606 - 바이러스
#include <iostream>
#include <vector>
using namespace std;

int visited[101]; // 방문 여부를 저장
vector graph[101]; // 연결 정보를 저장
int countInfected = 0; // 감염된 컴퓨터 수

void DFS(int node) {
    // 이미 방문한 노드라면 리턴
    if (visited[node]) return;

    visited[node] = 1; // 현재 노드 방문 처리
    countInfected++;   // 감염된 컴퓨터 수 증가

    // 연결된 모든 노드에 대해 DFS 수행
    for (int neighbor : graph[node]) {
        DFS(neighbor);
    }
}

int main() {
    int n, k;
    cin >> n >> k;

    // 연결 정보 입력
    for (int i = 0; i < k; i++) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a); // 양방향 연결
    }

    DFS(1); // 1번 컴퓨터부터 DFS 시작

    cout << countInfected - 1 << '\n'; // 1번 컴퓨터 제외 감염된 컴퓨터 수 출력
    return 0;
}

---

코드 설명

코드의 주요 로직과 사용된 알고리즘 설명.

• 핵심 알고리즘:
  • DFS(깊이 우선 탐색)을 사용하여 그래프를 탐색하며 감염된 컴퓨터 수를 계산합니다.
• 구현 세부사항:
  • graph: 연결 리스트 형태로 컴퓨터 간의 연결 정보를 저장합니다.
  • visited: 특정 컴퓨터가 이미 감염되었는지 여부를 확인합니다.
  • DFS: 1번 컴퓨터를 시작으로 연결된 모든 컴퓨터를 재귀적으로 방문합니다.
• 시간 복잡도 분석:
  • DFS 탐색: O(V + E), 여기서 V는 컴퓨터 수, E는 연결 정보의 수입니다.
  • 총 시간 복잡도: O(V + E)

---

결과

제출 시, 모든 테스트 케이스에 대해 올바른 결과를 출력합니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!