[백준] 2606번 바이러스

단계별로 풀어보기 DFS와 BFS의 2단계 문제

2606번: 바이러스

파이썬과 C++로 풀어보았다.

파이썬 코드

class Graph:
    def __init__(self, n):
        self.data = {}
        for i in range(1, n + 1):
            self.data[i] = set()
    def add_edge(self, n, m):
        self.data[n].add(m)
        self.data[m].add(n)
    def dfs(self, start):
        count = 0
        visited = [False] * (len(self.data) + 1)
        stack = []
        stack.append(start)
        while stack:
            cur = stack.pop()
            if not visited[cur]:
                count += 1
            visited[cur] = True
            temp = []
            for i in self.data[cur]:
                if not visited[i]:
                    temp.append(i)
            temp.sort()
            temp.reverse()
            stack.extend(temp)
        print(count - 1)

from sys import stdin

nodeCount = int(input())
edgeCount = int(input())
graph = Graph(nodeCount)
li = []
for i in range(0, edgeCount):
    rawInput = list(map(int, stdin.readline().split()))
    graph.add_edge(rawInput[0], rawInput[1])
graph.dfs(1)

C++ 코드

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

vector<int> w[101];
vector<bool> visited(101);


int main() {
	int numOfComputers;
	cin >> numOfComputers;
	int numOfEdge;
	cin >> numOfEdge;
	for (int i = 0; i < numOfEdge; i++) {
		int n, m;
		cin >> n >> m;
		w[n].push_back(m);
		w[m].push_back(n);
	}
	queue<int> q;
	q.push(1);
	while (!q.empty()) {
		int cur = q.front();
		q.pop();
		if (!visited[cur]) {
			visited[cur] = true;
			for (int i : w[cur]) {
				q.push(i);
			}
		}
	}
	int count = 0;
	for (int i = 1; i <= numOfComputers; i++) {
		if (visited[i]) count++;
	}
	cout << count - 1;
	return 0;
}

2월 4일에 이렇게 풀고 두 달 뒤인 4월 7일에 C++로 다시 풀어보았다.

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


int main() {
	int numOfComputers, n;
	cin >> numOfComputers >> n;
	vector<int> v[101];
	vector<bool> visited(numOfComputers + 1);
	for (int i = 0; i < n; i++) {
		int from, to;
		cin >> from >> to;
		v[from].push_back(to);
		v[to].push_back(from);
	}
	stack<int> s;
	s.push(1);
	while (!s.empty()) {
		int cur = s.top();
		s.pop();
		visited[cur] = true;
		for (int i = 0; i < v[cur].size(); i++) {
			if (!visited[v[cur][i]]) {
				s.push(v[cur][i]);
			}
		}
	}
	int cnt = 0;
	for (int i = 2; i <= numOfComputers; i++) {
		if (visited[i] == true)
			cnt++;
	}
	cout << cnt;
	return 0;
}

이번에는 DFS로 풀어보았다. 막 다른 길이 나왔을 때 가지치기를 빨리 하라고 DFS를 쓰긴 했는데 DFS를 쓰나 BFS를 쓰나 별 차이는 없을 것 같다.

이 문제는 가중치가 없는 무방향 그래프에서 1부터 탐색을 하면 된다. 그렇게 방문된 노드의 수에서 1을 빼면 그게 바이러스에 걸린 컴퓨터 대수이다. 바이러스든 뭐든 퍼트리는 것은 다 DFS, BFS라고 생각하면 된다.

그래프를 저장하는 방법은 벡터를 사용했다. 벡터의 배열을 사용해서 노드 i와 연결된 노드들은 v[i] 벡터에 push_back 해줘서 차곡차곡 넣어주었다.