[Python] 백준 2606번 : 바이러스

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

---

 

 

 

BFS

from collections import deque
import sys

N = int(sys.stdin.readline().rstrip())
E = int(sys.stdin.readline().rstrip())

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

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

def bfs(visited, graph, start):
    queue = deque([start])
    visited[start] = True

    while queue:
        v = queue.popleft()
        
        for i in graph[v]:
            if not visited[i]:
                queue.append(i)
                visited[i] = True

bfs(visited, graph, 1)
print(visited.count(True) - 1)

 

 

DFS

from collections import deque
import sys

N = int(sys.stdin.readline().rstrip())
E = int(sys.stdin.readline().rstrip())

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

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

def dfs(graph, visited, v):
    visited[v] = True
    
    for i in graph[v]:
        if not visited[i]:
            dfs(graph, visited, i)
    
dfs(graph, visited, 1)
print(visited.count(True) - 1)

 

 

• DFS BFS 기본 구현