[알고리즘] 백주 2606 바이러스 (파이썬 풀이)

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

2606번: 바이러스

해결코드

n = int(input())
m = int(input())
li = [[]*n for _ in range(n+1)]
for i in range(m):
    a,b = map(int, input().split())
    li[a].append(b)
    li[b].append(a)
cnt = 0
visited = [0]*(n+1)

def dfs(num):
    global cnt
    visited[num] = 1
    for i in li[num]:
        if visited[i]==0:
            dfs(i)
            cnt += 1
dfs(1)
print(cnt)

문제풀이

이 문제는 전형적인 dfs 유형을 가지고 있다.

원래 dfs문제를 풀던 대로 풀면 된다.

문제에서 친절하게 1번 컴퓨터를 통해 감염되는 컴퓨터 수를 구하라고 했으므로

1번 컴퓨터와 연결된 컴퓨터 수를 구하면 된다.

 

코드를 보자

 

n = int(input())
m = int(input())

컴퓨터의 수 n과 연결된 컴퓨터 쌍 수 m을 입력받는다.

 

li = [[]*n for _ in range(n+1)]

li라는 변수에 n개의 원소를 가진 n개의 리스트를 만들어서 저장해준다.

 

for i in range(m):
    a,b = map(int, input().split())
    li[a].append(b)
    li[b].append(a)

m개 만큼 for문을 돌린다.

a,b에 연결된 컴퓨터 쌍을 입력받고

li에 각각 추가해준다.

 

cnt = 0
visited = [0]*(n+1)

결과값을 저장할 cnt와 visited라는 방문 리스트를 만들어준다

(n+1개인 이유는 1부터 시작하기 때문이다)

 

def dfs(num):
    global cnt
    visited[num] = 1
    for i in li[num]:
        if visited[i]==0:
            dfs(i)
            cnt += 1

함수 dfs를 보면

전역변수로 cnt를 불러오고

visited(num)을 1로 바꿈으로써 방문처리를 해준다.

li[num]의 원소로 for문을 실행시킨다.

만약 원소들이 방문되지 않았다면

재귀해준다.

재귀하게 되면 cnt값을 1씩 더해준다.

 

dfs(1)
print(cnt)

1번 컴퓨터부터 시작하므로 dfs(1)을 실행시켜준다.

cnt값을 출력한다.