[Python] 백준 2606번 - 바이러스

📌 문제 링크

• 백준 2606번: 바이러스

⏰ 시간

• 25분

1. 문제 이해

그래프 연결 문제이다.
<그림 1>에서 볼 수 있듯이, 1번 컴퓨터에 의해 웜 바이러스에 노출되는 컴퓨터는 2, 3, 5, 6번 컴퓨터이다.

2. 코드 분석

input = open(0).readline 

computer_num = int(input())
connection = [[] for _ in range(computer_num+1)]

visited = [0 for _ in range(computer_num+1)]

def dfs(x, y, z):
    if visited[x] == 0:
        visited[x] = 1 
        for j in connection[x]:
            dfs(j, cnt, visited)
    
for i in range(n := int(input())):
    a, b = map(int, input().split())
    connection[a].append(b); connection[b].append(a)

cnt = 0
dfs(1, cnt, visited)

print(sum(visited)-1)

computer_num : 컴퓨터의 총 개수
connection : 컴퓨터의 입력 유무를 저장해둘 2차원 리스트
visited : 방문 여부 확인 리스트 (0: 방문X, 1: 방문O)

DFS (깊이 우선 탐색) - 재귀

<예제 1>

visited = [0, 0, 0, 0, 0, 0, 0, 0]

[재귀 1]

1번 컴퓨터 방문 -> visited = [0, 1, 0, 0, 0, 0, 0, 0]

1번 컴퓨터와 연결되고 방문안한 컴퓨터 = 2번, 5번

[재귀 2]

2번 컴퓨터 방문 -> visited = [0, 1, 1, 0, 0, 0, 0, 0]

2번 컴퓨터와 연결되고 방문안한 컴퓨터 = 3번

[재귀 3]

5번 컴퓨터 방문 -> visited = [0, 1, 1, 0, 0, 1, 0, 0]

5번 컴퓨터와 연결되고 방문안한 컴퓨터 = 6번

[재귀 4]

3번 컴퓨터 방문 -> visited = [0, 1, 1, 1, 0, 1, 0, 0]

3번 컴퓨터와 연결되고 방문안한 컴퓨터 = X

[재귀 5]

6번 컴퓨터 방문 -> visited = [0, 1, 1, 1, 0, 1, 1, 0]

6번 컴퓨터와 연결되고 방문안한 컴퓨터 = X

visited에서 0은 방문을 한 노드이고 1은 방문을 하지 않은 노드이다.
즉, visited의 합계에서 1을 뺀 값이 웜 바이러스에 노출된 컴퓨터의 개수와 동일하다.
1을 빼는 이유는 웜 바이러스에 노출된 컴퓨터의 개수에서 1번 컴퓨터는 제외해주어야 하기 때문이다.