빠켱이

백준 2606번 바이러스[C++] 본문

알고리즘/백준 알고리즘

백준 2606번 바이러스[C++]

빠켱이 2020. 9. 4. 15:01

2606은 1260번과 거의 흡사하게 bfs dfs의 기초 문제라고 볼 수 있습니다.

저는 2606번을 dfs를 사용하여 풀이하였습니다.

1260번을 풀이하셨다면 별다른 설명이 필요 없을 것 같은 문제입니다.

혹시 1260번을 풀지 않으셨다면 1260번을 먼저 푸는것을 추천드립니다. 1260 >> https://bbakyunge.tistory.com/10

#include <iostream>
#include <vector>

using namespace std;
vector<vector<int>> v;
vector<bool> visit;
int result = 0;
void dfs(int a);
int main() {
	int n, m, tmp1, tmp2;
	scanf("%d %d", &n, &m);
	v.resize(n + 1);
	visit.resize(n + 1);
	for (int i = 0; i < m; i++) {
		scanf("%d %d", &tmp1, &tmp2);
		v[tmp1].push_back(tmp2);
		v[tmp2].push_back(tmp1);
	}
	dfs(1);
	printf("%d", result - 1);
	return 0;
}
void dfs(int a) {
	result++;
	visit[a] = true;
	for (int i = 0; i < v[a].size(); i++) {
		if (!visit[v[a][i]]) {
			dfs(v[a][i]);
		}
	}
	return;
}

main문에서는 주어진 input값에 따라 그래프 연결상태를 완성시켰습니다. 기존 저의 1260번 풀이와 다른 점이라면 기존에는 배열을 사용하여 정점 번호를 index값을 사용해 연결된 곳은 1 연결되지 않은 곳은 0을 사용하였지만 해당 문제에서는 vector를 사용하여 해당 정점에 해당되는 index에 연결된 정점의 값을 push_back 해주었습니다.

이후에는 연결된 점들을 찾을 때마다 result++을 해주어 프로그램을 완성하였습니다.

 

Comments