[백준 2606] 바이러스 (python)

2606번: 바이러스

---

DFS로 탐색

1. 인접행렬과 방문흔적 남기는 배열을 생성한다
2. 방문하지 않았고, 연결되있는 것들을 체크한다.

import sys

input = sys.stdin.readline
N = int(input())
answer = 0


def dfs(x):
    global answer
    for i in range(N+1):
        if matrix[x][i] == 1 and check[i] == 0:
            answer += 1
            matrix[x][i] = 0
            matrix[i][x] = 0
            check[i] = 1
            dfs(i)


check = [0]*(N+1)
status = [0]*(N+1)
matrix = [[0]*(N+1) for _ in range(N+1)]
pair_N = int(input())
for _ in range(pair_N):
    x, y = map(int, input().split())
    matrix[x][y] = 1
    matrix[y][x] = 1

check[1] = 1
dfs(1)

print(answer)