[백준/Python] 2606번: 바이러스

문제

https://www.acmicpc.net/problem/2606

2606번: 바이러스

---

문제 요약

n개의 컴퓨터가 m개의 네트워크로 연결되어 있을 때, 1번 컴퓨터가 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 바이러스에 감염되는 컴퓨터 수를 출력한다.

 

두 컴퓨터가 네트워크로 연결되어 있을 때, 하나의 컴퓨터가 바이러스에 감염되면 다른 컴퓨터도 바이러스에 감염된다.

---

코드

def dfs(start):
    global cnt
    check[start] = 1
    for i in tree[start]:
        if not check[i]:
            cnt += 1
            dfs(i)

n = int(input())
# 컴퓨터 수

m = int(input())
# 컴퓨터 쌍 수

cnt = 0
# 바이러스에 감염된 컴퓨터 수

tree = [[] for _ in range(n+1)]
# i번 컴퓨터와 네트워크로 연결된 컴퓨터 번호를 저장하는 인접리스트

check = [0] * (n+1)
# 방문 체크 리스트

# 입력 받은 값을 인접리스트에 저장
for i in range(m):
    a, b = map(int, input().split())
    tree[a].append(b)
    tree[b].append(a)

# print(tree)

dfs(1) # 1번 컴퓨터부터 DFS 진행

print(cnt)

---

코드 설명

1. 입력 값을 인접리스트에 저장한다.

 

2. dfs함수를 통해 1번 컴퓨터부터 DFS 탐색을 진행한다.

 

2 - 1. 방문한 컴퓨터 번호를 check 배열에 1로 체크한다. (초기값: 0)

 

3. 탐색하며 바이러스에 감염된 컴퓨터 수를 출력한다.