백준 C++ | #29 BOJ2606 바이러스 C++ 문제 풀이

2606번: 바이러스 (acmicpc.net)

2606번: 바이러스

첫 DFS 문제! 

일단 이차원 배열에 그래프를 정의해주고, 

그 다음에 dfs 함수를 구현하고, 시작 노드를 dfs에 넣어 완전탐색을 시킨다. 

#include <iostream>
#include <vector>

int answer = 0;

void dfs(int x, int vertex, int edge, int** graph, int* visited) {
	visited[x] = 1;
	for (int i = 1; i <= vertex; i++) {
		if (graph[x][i] == 1 && !visited[i]) {
			answer++;
			dfs(i, vertex, edge, graph, visited);
		}
	}
}

int main() {
	int vertex, edge;

	std::cin >> vertex;
	std::cin >> edge;

	int** graph = new int*[vertex+1];
	int* visited = new int[vertex+1];

	for (int i = 0; i < vertex+1; i++) {
		graph[i] = new int[vertex+1];
		visited[i] = 0;
	}

	for (int i = 0; i < vertex + 1; i++) {
		for (int j = 0; j < vertex + 1; j++) {
			graph[i][j] = -1;
		}
	}

	for (int i = 0; i < edge; i++) {
		int x, y;
		std::cin >> x >> y;
		graph[x-1][y-1] = graph[y-1][x-1] = 1;
	}
	
	dfs(0, vertex, edge, graph, visited);
	
	std::cout << answer << std::endl;

	return 0;
}