백준 2606: 바이러스 (Python, C++) - dfs

문제

2606번: 바이러스

 

어제 풀었던 DFS와 BFS 문제와 거의 똑같은 문제이다. DFS로 단순하게 풀었다.

 

풀이1 (Python)

cnt = 0
def dfs(c):
    global cnt
    v[c]=1
    for i in range(1,n+1):
        if g[c][i]==1 and v[i]==0:
            cnt += 1
            dfs(i)

if __name__ == '__main__':
    n = int(input())
    pair = int(input())

    g = [[0] * (n + 1) for _ in range(n + 1)]
    v = [0] * (n + 1)

    for _ in range(pair):
        a,b = map(int,input().split())
        g[a][b] = g[b][a] = 1

    dfs(1)
    print(cnt)

 

풀이2 (C++)

#include <iostream>
using namespace std;
int N, link, com[101][101], visit[101], a, b,cnt;

void DFS(int n) {
	cnt++;
	visit[n] = 1;
	for (int i = 1; i <= N; i++) {
		if (com[n][i] && !visit[i])DFS(i);
	}
}

int main() {
	cin >> N;
	cin >> link;
	for (int i = 0; i < link; i++) {
		cin >> a >> b;
		com[a][b] = com[b][a] = 1;
	}
	DFS(1);
	cout << cnt - 1;
	return 0;
}