c언어 2606번 바이러스 (백준)

#include <stdio.h>

char map[101][101] = {0}; //x번째 컴퓨터와 관련있는 컴퓨터를 담는 배열
char visited[101] = {0}; //1과 관련이 있으면 1 없으면 0

void dfs(int k) 
{
	for(int i = 1; i<=map[k][0]; i++) {
		if(visited[map[k][i]] == 0) {
			visited[map[k][i]] = 1;
			dfs(map[k][i]);
		}
	}
}

int main(void)
{
	int ans = 0;
	int n = 0;
	scanf("%d", &n);
	
	int t = 0;
	scanf("%d", &t);
	while(t--)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		map[a][0]++;
		map[a][map[a][0]] = b;
		map[b][0]++;
		map[b][map[b][0]] = a;
	}
	dfs(1);
	for(int i = 2; i<=n; i++) if(visited[i] == 1) ans++;
	printf("%d", ans);
}

 

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

2606번: 바이러스

풀이

1) 배열을 이용하여, 특정 컴퓨터와 관련된 컴퓨터들을 저장해 놓는다.

2) 1번째 컴퓨터부터 dfs을 이용하여, 연관있는 컴퓨터를 찾고, 그 연관있는 컴퓨터를 dfs함수에 집어 넣는다.

(단 이미 연관이 있었다면, dfs함수에 집어 넣지 않는다)

연관이 있을 때마다 visited배열을 0에서 1로 만든다.

3) dfs가 끝나면 visited배열 중 값이 1 인 것들의 합을 구하면 된다.