[Python] 백준 2606번 : 바이러스 (S3) - DFS&BFS단계별2

#문제

www.acmicpc.net/problem/2606

2606번: 바이러스

#풀이 & 학습한 내용

"BFS나 DFS로 그래프를 순회해서 방문할 수 있는 정점을 찾는 문제"입니다. supremo7.tistory.com/174에서 구현한 DFS와 BFS코드를 조금만 변형하면 구현 가능했고, 이번 문제는 방문하지 않은 노드가 여러 개일 때, 꼭 번호가 낮은 순서부터 처리할 필요가 없어 아래 코드 35번째 줄 반복문에서 sort를 해주지 않았습니다.

 

#소스코드

from collections import deque
 
count = 0 #방문된 노드를 count
 
def dfs(graph,V,visited):
  global count
  visited[V]=True
  count+=1
  for i in graph[V]:
    if not visited[i]:
      dfs(graph,i,visited)
 
def bfs(graph,start,visited):
  global count
  queue=deque([start])
  visited[start]=True
  while queue:
    v = queue.popleft()
    visited[v]=True
    count+=1
    for i in graph[v]:
      if not visited[i]:
        queue.append(i)
        visited[i]=True
 
 
com = int(input())
net = int(input())
 
#방문여부 확인하는 리스트 초기화
visited=[False]*(com+1)
#인접리스트 초기화
graph = [[] for _ in range(com+1)]
 
for i in range(net):
  c1,c2=map(int,input().split())
  graph[c1].append(c2)
  graph[c2].append(c1)
 
#dfs(graph,1,visited)
bfs(graph,1,visited)
 
print(count-1) #1번 컴퓨터는 제외

 

github.com/HoYoungChun/Algorithm_PS/blob/master/DFS%26BFS/BOJ_2606.py

HoYoungChun/Algorithm_PS