[c/c++] 백준 2606 (Silver 3)

🔨 문제

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

1번 컴퓨터가 바이러스에 걸렸을 때 1번 컴퓨터를 통해 바이러스에 감염되는 컴퓨터의 수를 출력

🔨 해결방법

DFS - https://m42-orion.tistory.com/m/63
BFS - https://m42-orion.tistory.com/m/64
차이점 - https://velog.io/@lucky-korma/DFS-BFS%EC%9D%98-%EC%84%A4%EB%AA%85-%EC%B0%A8%EC%9D%B4%EC%A0%90

위의 블로그에서 도움을 많이 받았다.

깊이 우선 탐색(DFS, Depth First Search)

• dfs?
  그래프 전체를 탐색하는 방법
  하나의 가지(branch)를 모두 탐색한 이후에 다음 branch로 이동

  stack 또는 재귀함수로 구현

• 특징
  정점 방문 시, 정점 방문 여부를 검사하지 않으면 무한 루프에 빠질 수 있기 때문에 반드시 방문 여부를 검색해야 한다.

  bfs보다 메모리를 아낄 수 있다.

  얻은 결과가 최단 경로라는 보장이 없다.

너비 우선 탐색(BFS, Breadth First Search)

• bfs?
  그래프 전체를 탐색하는 방법
  현재 정점으로부터 가까운 정점들을 먼저 방문

  queue를 이용하여 구현

• 특징
  queue에 다음에 탐색할 정점들을 push하고 pop하는 과정을 거치기 때문에, dfs에 비해서 메모리가 더 필요하다.

  얻은 결과가 최단 경로임을 보장한다.

  목표 노드의 깊이 가 얕은 경우 dfs보다 더 빠르게 해답을 구할 수 있다.

자세한 실행 방식은 주석으로 확인

🔨 코드

DFS 이용

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

vector<vector<int>> graph;	//인접 리스트
//이중 vector 를 사용함으로써 필요한 메모리만 할당해서 사용할 수 있음
vector<bool> infected;	//정점 방문 여부 저장
queue <int> q;

void dfs(int start){
	infected[start] = true;

	for (int i = 0; i < graph[start].size(); i++) {
		int next = graph[start][i];
		if (!infected[next]) {
			dfs(next);	// 재귀함수
		}
	}
}


int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int n, line;	//정점의 개수, 간선의 개수
	cin >> n >> line;
	graph.assign(n + 1, vector<int>(0, 0));	//assign 함수를 통해서 vector<int>를 n+1개 할당
	infected.assign(n + 1, false); // 노드는 1~n, 모두 false로 초기화
	

	for (int i = 0; i < line; i++) {	//간선 연결
		int n1, n2;
		cin >> n1 >> n2;
		graph[n1].push_back(n2);
		graph[n2].push_back(n1);
	}
	
	dfs(1);	// bfs 시작 노드 1
	int total = 0;
	for (int i = 2; i <= n; i++) {	//이미 1번은 감염
		if (infected[i]) total++;
	}
	cout << total;
	
	return 0;
}

BFS 이용

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

vector<vector<int>> graph;	//인접 리스트
//이중 vector 를 사용함으로써 필요한 메모리만 할당해서 사용할 수 있
vector<bool> infected;	//정점 방문 여부 저장
queue <int> q;

void bfs(int start) {
	q.push(start);
	infected[start] = true;	// 시작 노드 방문 처리

	while (!q.empty()) {
		int cur = q.front();	// 큐에서 제일 앞에 있는 값을 꺼냄
		q.pop();
		for (int i = 0; i < graph[cur].size(); i++) {	//현재 노드의 인접한 노드들을 반복문을 통해 접근
			int next = graph[cur][i];	
			if (!infected[next]) {	// 감염됐는지 확인하고, 방문하지 않은 경우에만 노드를 큐에 삽입 -> 방문처리
				q.push(next);
				infected[next] = true;
			}
			
		}
	}
}

int main() {
	cin.tie(NULL);
	cout.tie(NULL);
	ios::sync_with_stdio(false);

	int n, line;	//정점의 개수, 간선의 개수
	cin >> n >> line;
	graph.assign(n + 1, vector<int>(0, 0));	//assign 함수를 통해서 vector<int>를 n+1개 할당
	infected.assign(n + 1, false); // 노드는 1~n, 모두 false로 초기화
	

	for (int i = 0; i < line; i++) {	//간선 연결
		int n1, n2;
		cin >> n1 >> n2;
		graph[n1].push_back(n2);
		graph[n2].push_back(n1);
	}
	
	bfs(1);	// bfs 시작 노드 1
	int total = 0;
	for (int i = 2; i <= n; i++) {	//이미 1번은 감염
		if (infected[i]) total++;
	}
	cout << total;
	
	return 0;
}