[백준] 2606 바이러스 파이썬 DFS/BFS

문제

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

2606번: 바이러스

 

그래프 탐색 문제이다. 1번 컴퓨터를 통해 웜 바이러스에 걸릴 컴퓨터의 개수를 구하면 된다.

즉, 1번 노드와 연결된 노드의 개수를 구하면 된다. 

DFS, BFS 두 가지 방법으로 문제를 풀 수 있다.

 

문제에서 연결된 컴퓨터의 정보를 알려줄 때, 그래프는 무방향 그래프임을 주의해야 한다.

 

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

 

따라서 위와 같은 input이 주어지면 

 

for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

위와 같은 방법으로 그래프 정보를 저장해주어야 한다.

---

 

정답

 

DFS 재귀 구현

import sys
 
input = sys.stdin.readline
 
N = int(input())
M = int(input())
 
graph = [[] for i in range(N + 1)]
visited = [False] * (N + 1)
 
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
 
def dfs(graph, v, visited):
     visited[v] = True
     for i in graph[v]:
         if not visited[i]:
             dfs(graph, i, visited)
 
 
 dfs(graph, 1, visited)
 
 res = list(filter(lambda x: x == True, visited))
 print(len(res) - 1)

 

BFS 큐 구현

import sys
from collections import deque
 
input = sys.stdin.readline
 
N = int(input())
M = int(input())
 
graph = [[] for i in range(N + 1)]
visited = [False] * (N + 1)
 
for _ in range(M):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)
    
def bfs(v):
    queue = deque([v])
    visited[v] = True
    while queue:
        x = queue.popleft()
        for i in graph[x]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True
 
 
bfs(1)
res = list(filter(lambda x: x == True, visited))
print(len(res) - 1)