백준 2606_바이러스(C++)

 

www.acmicpc.net/problem/2606

2606번: 바이러스

[문제 풀이]

DFS를 이용하여 문제를 풀었습니다.

 

이 문제는 전형적이 DFS 문제로 1과 직/간접적으로 연결된 컴퓨터의 개수를 찾는 문제입니다. 1과 연결 된 i의 컴퓨터를 찾고 i와 연결 된 j의 컴퓨터를 찾는 식의 문제로 해결할 수 있습니다. 

 

코드 설명

• 컴퓨터들의 연결을 2차원 배열에 나타냅니다.
• 1부터 n까지 반복하며 1과 연결 된 컴퓨터 i를 찾습니다.
• 1과 연결된 컴퓨터 i가 확인하지 않은 컴퓨터라면 i와 연결 된 컴퓨터들을 찾는 식으로 구현하였습니다.

[코드]

#include<iostream>
#include<vector>

using namespace std;

int n, m;

int map[101][101];
int visit[101];

vector<pair<int, int>> network;

void search(int idx) {

	for (int i = 1; i <= n; i++) {

		if (map[idx][i] == 1 && visit[i] == 0) {
			visit[i] = 1;
			search(i);
		}

	}

}

int main() {


	cin >> n >> m;

	for (int i = 0; i < m; i++) {
		int temp1, temp2;
		cin >> temp1 >> temp2;
		
		map[temp1][temp2] = 1;
		map[temp2][temp1] = 1;
	}

	visit[1] = 1;

	for (int i = 1; i <= n; i++) {

		if (map[1][i] == 1 && visit[i] == 0) {
			visit[i] = 1;
			search(i);
		}
	}

	int answer = 0;

	for (int i = 1; i <= n; i++)
		if (visit[i] == 1)
			answer++;

	cout << answer - 1<< endl;

	return 0;
}