[백준 2606] 바이러스

바이러스

문제설명

첫 줄(node)에 컴퓨터의 수, 두 번째 줄(num)에 간선의 수가 주어진다.
그리고 연결관계를 입력 받은 뒤, 1번 컴퓨터부터 시작해서 바이러스에 감염된 컴퓨터의 수를 출력시키는 문제이다.

---

알고리즘 설명

1. input을 입력받는다.
2. 연결관계를 2차원 배열에 graph[x][y]=1, graph[y][x]=1에 각각 넣어준다.
3. dfs 함수에서 현재 방문 노드를 매개변수로 받고 반복문을 1부터 노드의 수까지 반복하여 연결된 노드를 찾아 재귀적으로 방문한다.
4. 방문할 때 바이러스에 감염된 컴퓨터의 수도 같이 세어준다.

#include <stdio.h>
#include <stdlib.h>
#include <iostream>
#include <vector>
using namespace std;
#define MAX 101

int graph[MAX][MAX];
bool visited[MAX];
int node, num;
int answer = 0;
void DFS(int index)
{
    visited[index] = 1;

    for (int i = 1; i <= node; i++)
    {
        if (graph[i][index] == 1 && visited[i] == 0)//현재 방문한 노드의 오른쪽이 방문 가능하고 아직 가지 않은 경우
        {
            DFS(i);
            answer++;
        }
    }
}

int main(void)
{
    cin >> node>> num;
    int x, y;
    for (int i = 0; i < num; i++)//연결 관계 입력 받기
    {
        cin >> x >> y;
        graph[x][y] = 1;
        graph[y][x] = 1;
    }

    DFS(1);
    cout << answer << endl;
    return 0;
}

---

<2022년 다시 푼 버전>

#include <iostream>
#include <vector>
using namespace std;
int N, P, cnt = 0;
bool visited[101];
vector<int> v[101];

void dfs(int x) {
	cnt++;//바이러스 감염 컴퓨터 수
	visited[x] = true;
	for (int i = 0; i < v[x].size(); i++)//연결된 관계 판단 
	{
		int next = v[x][i];
		if (!visited[next]) {
			dfs(next);
		}
	}
}


int main() {
	
	cin >> N>>P; //N은 컴퓨터 수, P는 관계 수

	
	for (int i = 0; i < P; i++)//관계 입력 받기
	{
		int a, b;
		cin >> a >> b;
		v[a].push_back(b);
		v[b].push_back(a);
	}
	 
	dfs(1);//1번부터 조회
	cout << cnt-1;//1번은 걸려 있으므로 -1
	
}

 

 

단순 dfs구현 문제와 동일한 알고리즘이다.