[BOJ 2606] 백준 바이러스 풀이 - c++

사용언어 :  C++

 

 

 

문제풀이

* main함수에서 인접리스트 만들고 1에서 시작하는 dfs 돌려주기. 노드 방문할 때마다 result(답)증가

- 전역변수 설정

int computer_num; //총 컴퓨터 갯수
int pair_num; // 연결된 쌍 갯수
int network[101][101] = { 0 }; //2차원 배열로 만든 인접리스트 
bool visited[100] = { false }; //해당 컴퓨터가 방문됐는지 기록 저장
int result = 0; //답

 

(1) main함수에서 입력값들을 이용해 리스트만들기 (network[a][b], network[b][a] 둘 다 설정해줘야 함)

	cin >> computer_num;
	cin >> pair_num;
	for (int i = 0; i < pair_num; i++) {
		int a, b;
		cin >> a >> b;
		network[a][b] = 1;
		network[b][a] = 1;
	}

 

(2) dfs 함수 만들기 (재귀 이용)

void dfs(int x) {
	result++;
	visited[x] = true;
	for (int i = 1; i <= computer_num; i++) {
		if (network[x][i] && !visited[i]) //i가 dfs 실행하는 조건:x와 연결돼있으면서 방문되지 않아야 함
			dfs(i);
	}
	return;
}

 

전체코드

#include<iostream>
#include<vector>
using namespace std;
int computer_num;
int pair_num;
int network[101][101] = { 0 };
bool visited[100] = { false };
int result = 0;

void dfs(int x) {
	result++;
	visited[x] = true;
	for (int i = 1; i <= computer_num; i++) {
		if (network[x][i] && !visited[i])
			dfs(i);
	}
	return;
}

int main() {
	cin >> computer_num;
	cin >> pair_num;
	for (int i = 0; i < pair_num; i++) {
		int a, b;
		cin >> a >> b;
		network[a][b] = 1;
		network[b][a] = 1;
	}
	dfs(1);
	cout << result - 1;

}

 

 

---

총평

dfs,bfs 관련 문제였는데 아직 능숙하지도 않고 서툴러서 2차원배열로 풀었다. 방법 자체는 복잡하지 않은 것 같았지만 내가 부족해서 어려웠던 문제. 다른 블로그들도 참고하면서 코드를 다듬은 것 같다. 하다보면 늘겠지..

---

문제 출처

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

2606번: 바이러스