[DFS/BFS] 백준 #2606 바이러스 - Python

🗂️ 문제

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

 

💡 접근법

1번 컴퓨터가 웜 바이러스에 걸렸고, 이와 네트워크 상에 연결된 모든 컴퓨터가 바이러스에 걸리게 된다. 따라서 1번과 연결된 노드의 개수를 구하면 되는 문제이다.

 

DFS, BFS 두 가지 방식으로 모두 해결 가능하며, 아래는 DFS를 통해 푼 코드이다.

연결된 노드에 대해 방문처리를 해주므로, 최종적으로는 방문처리가 된 노드의 개수에서 1번 노드를 빼주면 된다.

 

😎 내 코드

import sys

N = int(sys.stdin.readline())
K = int(sys.stdin.readline())

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

for _ in range(K):
    a, b = map(int, sys.stdin.readline().split())
    graph[a].append(b)
    graph[b].append(a)

def DFS(v):
    visited[v] = True

    for g in graph[v]:
        if not visited[g]:
            DFS(g)
    

DFS(1)
print(sum(visited)-1)

 

✅ 정답 확인