바이러스
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
DFS
설명을 잘 읽어보면, 결국 1번 컴퓨터와 연결이 된, 즉 그래프를 형성하는 노드들은 모두 감염이 된다는 것을 알 수 있다. 따라서 그래프 전체를 탐색하는 데 사용하는 DFS 알고리즘을 사용하면 되겠다.
def dfs(graph, v, visited):
visited[v] = True
temp.append(v)
for i in graph[v]:
if not visited[i]:
dfs(graph, i, visited)
이전 포스팅에서 다룬 코드를 약간 변형하였다. 이유는, 문제에서는 1번 노드와 그래프로 이루어지지 않은 노드들도 분명히 존재하기 때문에, 이를 구분하기 위하여 temp라는 전역 배열을 사용하였다.
import sys
global temp
temp = []
N = int(input())
graph = [[]] * (N + 1)
visited = [False] * (N + 1)
for i in range(N):
graph[i + 1] = [] #0번 인덱스를 제외한 나머지 인덱스에 리스트 부여
k = int(input())
for j in range(k):
a, b = map(int, sys.stdin.readline().split())
graph[a].append(b) #1번 노드와 2번 노드가 연결되면
graph[b].append(a) #2번 노드와 1번 노드도 연결되는 것이기 때문
dfs(graph, 1, visited)
print(len(temp)-1)#1번 노드 제외 출력
dfs 과정을 거치게 되면, 예제에 주어진 4-7 은 1번 노드와 연결되지 않은 독립적인 그래프이기 때문에, 탐색하지 않고, 1번 노드 밑에 있는 그래프만 temp 배열에 저장되어서 나오게 된다.
temp라는 배열은, 1번 노드와 인접한 그래프의 정보를 담게 되고, 문제에선 1번 노드에 의해 감염되는 컴퓨터의 개수를 구하라고 하였으므로, 배열의 길이에서 1을 빼준 뒤 출력하면 원하는 답을 얻게 된다.
