[C] 백준 - 2606번: 바이러스

5월 15일(월) - 그래프와 순회 (2606번)

2606번: 바이러스

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

최초 생각 정리

- 문제를 읽어보니, dfs를 활용해서 풀이를 진행해야겠다고 판단함

- 컴퓨터의 수는 변수 num으로, 직접 연결되어있는 컴퓨터 쌍의 수는 변수 connected로 입력받는다

- 컴퓨터의 번호 쌍은 for문에서 변수 connected를 사용해서 돌리면서, 변수 from과 to로 입력받는다

- dfs 함수에는 시작하는 vertex와 변수 num을 넘겨준다 -> 시작하는 vertex는 다시 변수 start로 받아준다

- dfs 함수의 내용은 기본적인 깊이우선탐색의 내용으로 설정

  그런데 최종출력할 변수 result 그리고 변수 num은 main 함수와 dfs 함수에서 모두 활용해야함

  -> 전역변수로 설정

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

문제점

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ

 

풀이

#define _CRT_SECURE_NO_WARNINGS
#pragma warning(disable: 4996)

#include <stdio.h>

int arr[101][101];
int visited[101];
int num, connected;
int result = 0;

void dfs(int start, int num)
{
	if (visited[start] == 1)
	{
		return;
	}

	visited[start] = 1;
	for (int i = 1; i <= num; i++)
	{
		if (arr[start][i] == 1 && visited[i] == 0)
		{
			result++;
			dfs(i, num);
		}
	}
	return;
}

int main(void)
{
	int num, connected;
	scanf("%d %d", &num, &connected);

	int from, to;
	for (int i = 0; i < connected; i++)
	{
		scanf("%d %d", &from, &to);
		arr[from][to] = 1;
		arr[to][from] = 1;
	}

	dfs(1, num);
	printf("%d", result);
	return 0;
}

ㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡㅡ