1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
입력은 이렇게 주어진다.
1 2
2 3
1 5
5 2
5 6
4 7
그림으로 나타내면 다음과 같다.
그림으로 그려서 생각하면 쉬운데 코드를 짜려니 어떤 식으로 접근 해야 할 지 막막했다.
코드 아이디어는 다음과 같다.
입력으로 주어진 노드(컴퓨터)들의 연결 상황을 나타내는 그래프를 만든다.
그런 다음 이 연결 그래프들을 DFS를 통해 순회하는데, 이 때 노드들의 방문 여부를 나타내는 체크리스트를 만들어 이에 표시한다.
순회가 다 끝난 뒤, 체크리스트에 표시(1) 되어있는 노드들의 합을 구하면 된다. (이 때 1번 노드로 인해 바이러스가 걸린 노드들의 수를 구하는 것이므로 1번 노드는 제외한 수를 센다.)
n = int(input()) # 컴퓨터의 수
m = int(input())
graph = [[] for _ in range(n+1)] # 그래프
checklist = [0] * n+1
# 그래프 만들기
for i in range(m):
a, b = map(int, input().split())
graph[a].append(b) # 양방향으로 연결한다.
graph[b].append(a) # 양방향으로 연결한다.
print(graph)
# [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
def dfs(v):
checklist[v] = 1 # 방문했다고 표시한다.
for i in graph[v]:
if checklist[i] == 0: # 방문하지 않은 노드에 한해
dfs(i) # dfs
dfs(1) # 1번 컴퓨터로부터 걸린 바이러스니까
print(sum(checklist)-1)
# def dfs():
