[백준/baekjoon] Silver3 2606. 바이러스

DFS 연습 2일차

DFS 재밌네

 

#include<iostream>
#include<vector>

using namespace std;

vector<bool> visited;
vector<vector<int>> adj;
int cnt = 0;

void dfs(int current) {
	visited[current] = true;

	for (int a : adj[current]) {
		if (visited[a]) continue;

		cnt++;
		dfs(a);
	}
}

int main() {
	int computer, connected;

	cin >> computer >> connected;
	adj = vector<vector<int>>(computer+1);
	visited = vector<bool>(computer + 1);

	int x, y;
	for (int i = 0; i < connected; i++) {
		cin >> x >> y;

		adj[x].push_back(y);
		adj[y].push_back(x);
	}

	dfs(1);

	cout << cnt;
}

---

문제

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

2606번: 바이러스

728x90

---

[접근]

DFS

https://jolly-note.tistory.com/62?category=993245 

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

---

[접근1]

adj와 visited의 크기를 초기화해주고 연결된 computer들을 양측에 입력해준다.

computer 1부터 감염을 시작한다.

cin >> computer >> connected;
adj = vector<vector<int>>(computer+1);
visited = vector<bool>(computer + 1);

int x, y;
for (int i = 0; i < connected; i++) {
    cin >> x >> y;

    adj[x].push_back(y);
    adj[y].push_back(x);
}

dfs(1);

---

[접근2] - dfs 내부

현재 노드의 visited 상태를 true로 바꿔준다.

현재 노드의 인접 노드들을 돌면서 만약 이미 방문했다면 넘어가고 아니면 cnt 값을 증가시켜준 뒤 해당 노드로 다음 dfs를 진행한다.

void dfs(int current) {
	visited[current] = true;

	for (int a : adj[current]) {
		if (visited[a]) continue;

		cnt++;
		dfs(a);
	}
}