2606. 바이러스

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

# 문제 설명

기본적인 완전탐색 문제였다.
1번 컴퓨터에서 방문할 수 있는 모든 컴퓨터의 개수를 출력하면 되는 문제이다.

쉽게 말해서, 1번 컴퓨터(노드)에 연결되어 있는 컴퓨터를 모두 탐색하면서 새로운 컴퓨터에 방문할 때마다 결과값(초기값은 0, int result)을 1씩 증가시켜주고 이를 출력하면 된다.
단, 1번 컴퓨터 자신은 제외된다. 즉, 1번 컴퓨터에서 방문할 수 있는 컴퓨터가 존재하지 않으며 결과값은 0이 되어야 한다.

# 문제 풀이

형태를 보니 BFS보다는 DFS가 구현이 좀 더 간단할 것이란 판단에, DFS 방식으로 풀었다.
컴퓨터간의 연결관계를 vector edge[101]에 저장하기 위해 이 벡터를 선언하고, 이 컴퓨터를 방문했는지의 여부를 저장하는 int visit[101], 위에서 서술한 결과값은 result, 컴퓨터의 개수는 N, 연결관계(edge)의 개수는 M으로 선언하였다.

연결관계를 입력받을 때, 예를 들어 1 2로 주어지면 1에서도 2를 방문할 수 있고 2에서도 1을 방문할 수 있는 양방향 접근이 가능한 엣지이기 때문에 edge[1].push_back(2)로도 추가하고, edge[2].push_back(1)로도 추가하는 방식으로 연결관계를 입력 받았다.

방문은 문제에서 주어진 대로 1번 컴퓨터부터 시작( DFS(1) )하고,
점을 방문하면 visit[현재 방문하고 있는 점] = 1로 하여 방문 표시를 한다.
현재 방문하고 있는 점이 1이 아니면 1을 통해 갈 수 있는 컴퓨터의 개수인 result를 증가시켜주고, 현재 방문한 컴퓨터에서 접근할 수 있는 다음 컴퓨터가 있다면 계속해서 방문하고 없다면 DFS를 종료하고, 결과값을 출력한다.

// 2606. 바이러스
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

int N, M;
int visit[101];
int result;
vector<int> edge[101];

void DFS(int v) {
	visit[v] = 1;
	if (v != 1) result++;
	for (int i = 0; i < edge[v].size(); i++) {
		int next_v = edge[v][i];
		if (visit[next_v]) continue;
		DFS(next_v);
	}
}

int main() {
	cin >> N;
	cin >> M;
	for (int i = 1; i <= M; i++) {
		int v1, v2;
		cin >> v1 >> v2;
		edge[v1].push_back(v2);
		edge[v2].push_back(v1);
	}
	DFS(1);
	cout << result << endl;
}

# 고찰

1년 전에 같은 문제를 풀었을 때보다 코드가 꽤 간결해졌다.
오늘 2667 단지번호붙이기와 2644 촌수계산도 풀이했는데, 7569 토마토 문제를 풀고나서 함께 리뷰할 예정이다.