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

Siri·2022년 5월 13일
0

백준

목록 보기
1/2

[실버3]
문제 링크 : https://www.acmicpc.net/problem/2606

예제 입력 1


7
6
1 2
2 3
1 5
5 2
5 6
4 7

예제 출력 1


4

전체 코드


def dfs(v=1): #시작 기본값 1번 컴퓨터
    visited[v]=True
    for i in graph[v]:
        if not visited[i]:
            dfs(i)

n=int(input())

graph=[[] for _ in range(n+1)]
visited=[False]*(n+1)

for _ in range(int(input())):
    x,y=map(int,input().split())
    graph[x].append(y)
    graph[y].append(x)
dfs()
print(sum(visited)-1)

설명


기본 DFS 알고리즘을 그대로 구현하고
마지막에 방문개수 -1만 해주면 되는 간단한 문제이다.

방문한 노드의 수 -1 = 감염된 컴퓨터의 수 -1 = 1번이 감염시킨 컴퓨터의 수

0개의 댓글