[백준 2606] 바이러스

ssungho·2023년 7월 5일
0

BAEKJOON

목록 보기
8/12
post-thumbnail

바이러스 [C++]

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

난이도: ⚪⚪⚪


문제 설명


문제 접근

  1. 바이러스는 연결된 컴퓨터에 전파되기 때문에 BFS 또는 DFS를 이용하여 연결된 컴퓨터를 구한다.
  2. 연결된 컴퓨터를 한 쌍씩 입력받기 때문에 인접 리스트를 만들어 탐색한다.
    • 연결된 것을 확인하는 것이 중요하기 때문
  3. 1번 컴퓨터를 통해 바이러스에 걸리게 되는 컴퓨터의 수를 구하면 되기 때문에 1번 컴퓨터부터 DFS를 실행해 재귀되는 횟수로 전염되는 컴퓨터의 수를 구할 수 있다.

제출 코드

#include <iostream>
#include <vector>
using namespace std;

// 컴퓨터의 인접리스트와 감염된 컴퓨터 번호 리스트
vector<int> computers[101];
bool infected[101];
// 감염된 횟수
int cnt = -1;

// DFS 구현
void DFS(int computer_number)
{
    infected[computer_number] = true;
    cnt++;

    for(int i = 0; i < computers[computer_number].size(); i++)
        if(!infected[computers[computer_number][i]])
            DFS(computers[computer_number][i]);
}

// 메인 함수
int main(void)
{
    int computer_number, edge;
    cin >> computer_number >> edge;

	// 양뱡향으로 입력한다.
    int num1, num2;
    for(int i = 0; i < edge; i++)
    {
        cin >> num1 >> num2;
        computers[num1].push_back(num2);
        computers[num2].push_back(num1);
    }
    // 1번 컴퓨터부터 DFS 실행한다.
    DFS(1);
    cout << cnt;
    return 0;
}

결과

profile
클라이언트 개발자가 되는 그날까지 👊

0개의 댓글

Powered by GraphCDN, the GraphQL CDN