[백준][C++] 2606 바이러스

2606. 바이러스
문제 풀이

2606번: 바이러스

 

재귀를 사용한 DFS로 푼 문제.

 

연결되어있는 컴퓨터들은 전부 바이러스에 걸리기 때문에 인접행렬을 사용해 DFS로 인접한 노드들을 타고 타고 들어가서 체크를 해주었다.

 

1부터 시작해서 각 정점을 방문할 때마다 count 변수를 1씩 증가시켜주었다.

 

코드

#include <bits/stdc++.h>
using namespace std;

bool arr[101][101];
bool visited[101];
int cnt, len, answer;

void DFS(int n);

int main()
{
    cin >> cnt >> len;

    while (len--)
    {
        int num1, num2;
        cin >> num1 >> num2;

        arr[num1][num2] = arr[num2][num1] = true;
    }

    DFS(1);
    cout << answer;
}

// DFS
void DFS(int n)
{
    visited[n] = true;

    for (int i = 2; i <= cnt; i++)
    {
        // 방문하지 않았고 연결된 요소를
        if (arr[n][i] && !visited[i])
        {
            DFS(i);
            answer++;
        }
    }
}

 

만약 이 코드대로 예제 탐색을 한다면....

1
1 2
1 2 3
1 2 3 5
1 2 3 5 6

이 순서로 탐색이 될 것이다.

기초적인 그래프 탐색 문제!