[백준/C++] 2606번: 바이러스 (플로이드 와샬/DFS/BFS)

플로이드 와샬 알고리즘을 공부했다. 이 방법은 모든 정점에서 모든 정점으로의 최단경로를 구하는 방법이라고 한다. 이 문제의 경우 연결되었냐 or 연결되지 않았느냐 판단하는 문제여서 경로를 구할 필요도 없고 모든 정점에 대해 판단하지 않고, 첫번째 컴퓨터를 기준으로 판단하기 때문에 굳이 플로이드 와샬을 쓸 필요가 없지만 쉬워서 이걸로 풀었다. 오늘은 dfs, bfs로도 풀어봐야지. 3중 for문을 다 돌았을 때, 연결되어있는 노드라면 inf 가중치를 갖지 않을 것이다 라고 하고 풀었다.

플로이드 와샬 풀이

 

#include<iostream>
#define inf 99999
using namespace std;


int map[101][101];
int computer;
int main() {

	
	int N;
	pair<int,int> pair;
	
	cin >> computer >> N;
	for (int i = 1; i <= computer; i++) {
		for (int j = 1; j <= computer; j++) {
			map[i][j] = inf;
		}
	}

	for (int i = 0; i < N; i++) {
		cin >> pair.first >> pair.second;
		map[pair.first][pair.second] = 1;
		map[pair.second][pair.first] = 1;
	}

	//거쳐가는 노드
	for (int k = 1; k <= computer; k++) {
		//시작노드
		for (int i = 1; i <= computer; i++) {
			//끝노드
			for (int j = 1; j <= computer; j++) {
				if (map[i][k] + map[k][j] < map[i][j]) map[i][j] = map[i][k] + map[k][j];

			}
		}
	}

	
	int cnt = 0;
	for (int i = 2; i <= computer; i++) {
		if (map[1][i] != inf)cnt++;
	}
	cout << cnt;

}

 

DFS 풀이 

 

DFS로 쉽게(?)들 푼다는데 나는 DFS 초보라서 또 어려웠다. 그나마 BFS보다 DFS가 익숙해서 좀 더 빨리 푼듯....

 

#include<iostream>

using namespace std;


int computer;

int map[101][101];
int visit[101];
int cnt = 0;

void dfs(int x) {

	
	for (int i = 1; i <= computer; i++) {
		if (map[x][i] == 1 && visit[i] != 1) {
			cnt++;
			visit[i] = 1;
			dfs(i);
		}
	}


	
}

int main() {

	int N;
	pair<int,int> pair;
	
	cin >> computer >> N;

	for (int i = 0; i < N; i++) {
		cin >> pair.first >> pair.second;
		map[pair.first][pair.second] = 1;
		map[pair.second][pair.first] = 1;
	}
	/*
	for (int i = 1; i <= computer; i++) {
		for (int j = 1; j <= computer; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}

	*/

	visit[1] = 1;
	dfs(1);
	/*
	for (int i = 1; i <= computer; i++) {
		cout << visit[i] << " ";
	}
	
	*/

	cout << cnt;

}

 

BFS 풀이

BFS도 결국 탐색 순서만 다를 뿐 연결된 곳들은 다 탐색하기 때문에 BFS로도 풀 수 있다. BFS는 세상 어색하다..후....^^ 그래도 결국품

 

#include<iostream>
#include<queue>
using namespace std;


int computer;
int map[101][101];
int visit[101];
int cnt = 0;


queue<int> q;
void bfs(int x) {
	q.push(x);
	while (!q.empty()) {
		int y = q.front();
		q.pop();
		for (int i = 1; i <= computer; i++) {
			if (map[y][i] == 1 && visit[i] == 0) {
				cnt++;
				visit[i] = 1;
				q.push(i);
			}
		}
	}

}

int main() {

	int N;
	pair<int,int> pair;
	
	cin >> computer >> N;

	for (int i = 0; i < N; i++) {
		cin >> pair.first >> pair.second;
		map[pair.first][pair.second] = 1;
		map[pair.second][pair.first] = 1;
	}
	/*
	for (int i = 1; i <= computer; i++) {
		for (int j = 1; j <= computer; j++) {
			cout << map[i][j] << " ";
		}
		cout << endl;
	}

	*/

	visit[1] = 1;
	bfs(1);
	/*
	for (int i = 1; i <= computer; i++) {
		cout << visit[i] << " ";
	}
	
	*/

	cout << cnt;

}