BOJ 2606 바이러스

개요

BOJ 2606 바이러스

• 백준 온라인 저지 2606번 문제
• BOJ 31단계

C++

BFS

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> G[101];
bool visited[101];
int cnt = 0;
int u, v;

void bfs() {
    queue<int> q;
	visited[1] = true;
    q.push(1);
	while(!q.empty()) {
	    u = q.front();
	    q.pop();
	    for(int i=0; i<G[u].size(); i++) {
	        v = G[u][i];
	        if(!visited[v]) {
	            cnt++;
	            visited[v] = true;
	            q.push(v);
	        }
	    }
	}
}

int main() {
	scanf("%d", &N);
	scanf("%d", &M);
	for(int i=0; i<M; i++) {
		scanf("%d %d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	bfs();
	printf("%d", cnt);
}

DFS

#include <bits/stdc++.h>
using namespace std;

int N, M;
vector<int> G[101];
bool visited[101];
int cnt = -1;
int u, v;

void dfs(int x) {
	if (visited[x]) {
		return;
	}
	visited[x] = true;
	cnt++;
	for (int i=0; i<G[x].size(); i++) {
		dfs(G[x][i]); 
	}
}

int main() {
	scanf("%d", &N);
	scanf("%d", &M);
	for(int i=0; i<M; i++) {
		scanf("%d %d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
	dfs(1);
	printf("%d", cnt);
}