[백준/Python] 2606 바이러스

 

 

• dfs와 used를 통해 한번 들렀던 곳은 다시 들르지 않음으로써 dfs가 실행된 횟수만큼 카운트를 해주었다.

N = int(input())
M = int(input())

arr = [[0]*N for _ in range(N)]
used = [0] * N
cnt = 0

for i in range(M):
    y,x = map(int,input().split())

    arr[y-1][x-1] = 1
    arr[x-1][y-1] = 1

def dfs(now): # 1과 연결되어있는 정점의 수 만큼 cnt해줌
    global cnt

    for i in range(N):
        if arr[now][i] == 1 and used[i] == 0:
            used[i] = 1
            cnt += 1
            dfs(i)

used[0] = 1 # used배열, 자기 자신을 1로 만들고 dfs실행
dfs(0)
print(cnt)