[백준 / C언어] 2606번: 바이러스

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

2606번: 바이러스

 

난이도: solved.ac 실버 3

 

 

DFS를 이용하면 쉬운 문제다

(BFS로 풀어도 될 것 같음)

 

각 컴퓨터끼리의 연결을 그래프로 나타내서 arr라는 2차원 배열에 각 노드의 연결을 나타내주고

 

visited라는 1차원 배열에 컴퓨터의 방문을 나타내주었다

 

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define MAX 101

int arr[MAX][MAX];
int visited[MAX];
int cnt = 0;

void DFS(int x, int N);

int main() {
	int N, M, i, j;
	scanf("%d %d", &N, &M);
	int a, b;
	for (i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		arr[a][b] = 1;
		arr[b][a] = 1;
	}
	DFS(1, N);
	printf("%d", cnt);
	return 0;
}

void DFS(int x, int N) {
	visited[x] = 1;
	for (int i = 1; i <= N; i++) {
		if (!visited[i] && arr[x][i]) {
			cnt++;
			DFS(i, N);
		}
	}
}