[백준/Python] 2606번 - 바이러스

문제

2606번 - 바이러스

문제 해결 과정

• 최단 거리를 구하는 게 아니라서 특정 노드를 깊게 탐색하는 DFS를 사용

시행착오

• count를 어디서 +1 해야할지 헷갈렸음 global로 선언하고 dfs함수 안에서 +1하도록 했음 갯수 구하는 문제에서 count를 어디에 두는 지 확인하기
• 감염된 컴퓨터의 갯수를 구하는 반복문은 따로 구현해줘야한다는 것 한꺼번에 해결할려고 하지 말기. 갯수를 알기위한 반복문은 따로 구현
• 깊게 탐색하다가 연결되 노드가 없어서 탐색을 멈추고 다른 노드로 넘어갈 때 break을 하고자 함 break을 잘 이용하기
  • 그래서 감염된 컴퓨터의 갯수 구하는 반복문에 break을 작성

import sys

n = int(sys.stdin.readline())

num = int(sys.stdin.readline())

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

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

# DFS 구현
def dfs(graph,v,visited):
  global count
  visited[v] = True
  for i in graph[v]:
    if not visited[i]:
      count += 1
      dfs(graph,i,visited)
      
# 웜이 감염된 컴퓨터의 갯수 구하기
for i in range(1,n+1):
  if visited[i] == False:
    dfs(graph,i,visited)
    break
    
print(count)
  

21.07.21

BFS 풀이

import sys
from collections import deque

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
graph = [[] * m for _ in range(n+1)]
cnt = 0
visited = [False] * (n+1)

for _ in range(m):
  a,b = map(int,sys.stdin.readline().split())
  graph[a].append(b)
  graph[b].append(a)
  
def bfs(start):
  global cnt
  q = deque([start])
  visited[start] = True
  while q:
    v = q.popleft()
    for i in graph[v]:
      if not visited[i]:
        cnt += 1
        visited[i] = True
        q.append(i) 
bfs(1)     
print(cnt)