문제 링크

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

문제 풀이

1번 컴퓨터로부터 연결된 모든 컴퓨터를 출력하는 문제이기 때문에 깊이 탐색 알고리즘을 이용하였으며, 입력이 단방향으로 주어지기때문에 2차원 배열을 이용하여 연결쌍의 정보를 저장하여 문제를 풀었다.

변수

• int computerNum : 컴퓨터의 수
• int pairNum : 연결쌍의 개수
• int virusCnt : 바이러스에 걸린 컴퓨터의 수
• int map[MAX][MAX] : 연결된 컴퓨터의 정보가 담긴 배열( 두 컴퓨터가 연결되어있다면 1 그렇지 않다면 0 )
• bool visited[MAX] : 방문여부 확인을 위한 배열

함수

• void dfs(int idx) : 깊이 탐색 알고리즘

정답 코드

#include<iostream>
#define MAX 101
using namespace std;

int computerNum; // 컴퓨터의 개수 
int pairNum; // 컴퓨터 쌍의 수 

int map[MAX][MAX] = { 0, };
bool visited[MAX] = { false };
int virusCnt = -1;

void dfs(int idx) {
	visited[idx] = true;
	virusCnt++;
	for (int i = 1; i <= computerNum; i++) {
		if (map[idx][i] == 1 && visited[i] == false) {
			dfs(i);
		}
	}
}

int main() {
	cin >> computerNum >> pairNum;
	for (int i = 1; i <= pairNum; i++) {
		int temp;
		int temp2;
		cin >> temp >> temp2;
		map[temp][temp2] = 1;
		map[temp2][temp] = 1;
	}
	dfs(1);
	cout << virusCnt;
}