ShaShaKa Dev Note

바이러스

18 September 2019

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

이번은 BFS나 DFS로 그래프를 순회해서 방문할 수 있는 정점을 찾는 문제를 풀어보도록 하겠습니다.

#include<stdio.h>

static int N;
static int visited[101] = { 0 };
static int graph[101][101] = { 0 };
static int count = 0;

void dfs(int val);

int main(void) {

	int M, x, y;
	scanf("%d", &N);
	scanf("%d", &M);

	for (int i = 0; i < M; i++)
	{
		scanf("%d %d", &x, &y);
		graph[x][y] = 1;
		graph[y][x] = 1;
	}

	dfs(1);

	if (count == 0)
	{
		printf("%d", count);
	}
	else {
		printf("%d", count - 1);
	}
}

void dfs(int val) {
	if (visited[val] == 1)
	{
		return;
	}

	visited[val] = 1;
	count++;

	for (int i = 1; i <= N; i++)
	{
		if (graph[val][i] == 1 || graph[i][val] == 1) {
			dfs(i);
		}
	}
}

dfs의 구현이 간단하니, dfs로 풀어보도록 합니다.
각 정점을 순회하면서 방문하지 않은 점이면 count를 올려주고 모든 순회가 끝나면 count의 값을 return해주도록 합니다.
이 때, 문제에서 1번 컴퓨터를 통해 감염되는 컴퓨터의 수를 return하라고 하였으므로, 1번 컴퓨터를 제외한 값이 count-1을 return해줍니다.
다만, count값이 0인 경우는 그대로 return해주도록 합니다.