[백준 2606] 바이러스 cpp-py

문제
한 컴퓨터가 바이러스에 걸리면 그 컴퓨터와 연결되어 있는 모든 컴퓨터가 바이러스에 걸린다.
어느 날 1번 컴퓨터가 바이러스에 걸렸다면 1번 컴퓨터를 통해 바이러스에 걸리게 된느 컴퓨터의 수를 출력하라.

입력
첫째 줄에 컴퓨터의 수가 주어진다. (100이하)
둘째 줄에는 네트워크 상에 직접 연결되어 있는 컴퓨터 쌍의 수가 입력되고 이어서 그 수만큼 연결되어 있는 컴퓨터의 번호 쌍을 입력한다.

출력
1번 컴퓨터가 바이러스에 걸렸을 때 바이러스에 걸리게되는 컴퓨터의 수를 출력하라. (1번은 제외하고)

---

접근

연결되어있는 컴퓨터를 2차원 배열에서 무방향 그래프처럼 표현한다. 만약 1-2가 연결되어 있다면 2차원 배열에서 (1, 2)와 (2,1)을 모두 1로 표시한다. 그리고 DFS를 진행하며 방문을 기록하여 중복되어서 반복하지 않도록 한다.

 

구현

컴퓨터의 수와 연결된 컴퓨터의 쌍을 입력한다.

연결된 컴퓨터를 2차원 배열에서 무방향 그래프처럼 1로 표현한다.

바이러스는 1번 컴퓨터에서부터 시작되기 때문에 DFS에 1을 전달한다.

cin >> com >> N;

for (int i = 0; i < N; i++) {
	int y, x;
	cin >> y >> x;
	map[y][x] = map[x][y] = 1;
}

// 1번에서 바이러스가 퍼짐
DFS(1);

 

입력된 컴퓨터의 번호에 대해 바이러스가 침투했다는 표시로 bool형의 virus에 true로 표시한다. 이는 방문한 컴퓨터를 또다시 방문하지 않도록하는 효과도 있다.

이후 입력된 컴퓨터 번호를 기준으로 가로로 탐색을 한다. 여기서 연결되고 방문하지 않은 컴퓨터가 있다면 해당 번호를DFS에 전달한다. 

이 과정을 거치게되면 1번과 연결된 모든 컴퓨터가 바이러스에 걸리게된다.

void DFS(int c) {
	virus[c] = true;

	for (int i = 1; i <= com; i++) {
		if (virus[i] == false && map[c][i] == 1) {
			DFS(i);
		}
	}
}

 

virus에서 true의 개수를 answer를 증가시키면서 카운트한다.

최종적으로 1번을 제외한 바이러스 개수를 출력한다.

int answer = 0;
for (int i = 1; i <= com; i++) {
	if (virus[i])
		answer++;
}

cout << answer - 1 << endl;

---

전체 코드

 

c++

#include <iostream>
#include<algorithm>
#include <vector>
#include<queue>

using namespace std;

int com, N;
int map[101][101];
bool virus[101];

void DFS(int c) {
	virus[c] = true;

	for (int i = 1; i <= com; i++) {
		if (virus[i] == false && map[c][i] == 1) {
			DFS(i);
		}
	}
}
int main()
{
	cin >> com >> N;

	for (int i = 0; i < N; i++) {
		int y, x;
		cin >> y >> x;
		map[y][x] = map[x][y] = 1;
	}

	DFS(1);

	int answer = 0;
	for (int i = 1; i <= com; i++) {
		if (virus[i])
			answer++;
	}

	cout << answer - 1 << endl;
	return 0;
}

/*
0 1 2 3 4 5 6 7
1 - V - - V - -
2 V - V - V - -
3 - V - - - - -
4 - - - - - - V
5 V V - - - V -

BOOL 1차원 배열 생성 -> 탐색유무
탐색했으면 CONTINUE 안했으면 TRUE로 표시 
최종적으로 TRUE로 표시된 컴퓨터 출력

탐색방법 -> DFS
1번부터 시작 -> 2번 발견 TRUE변경 -> 2번으로 이동
*/

 

python

def DFS(com):
    virus[com] = False

    for c in range(1, N+1):
        if network[com][c] == 1 and virus[c]:
            DFS(c)


N = int(input())
M = int(input())

network = [[0 for _ in range(N+1)] for _ in range(N+1)]
virus = [True for _ in range(N+1)]
for _ in range(M):
    y, x = map(int, input().split())
    network[y][x] = network[x][y] = 1

DFS(1)
answer = 0
for idx in range(1, N+1):
    if not virus[idx]:
        answer += 1
print(answer-1)