[bfs] 백준 #2606 바이러스

문제

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

풀이

from collections import deque

n = int(input())
pair = int(input())

computer = [[] for _ in range(n+1)] # 연결된 컴퓨터 그래프
visited = [0]*(n+1) # 감염된 컴퓨터인지 아닌지 확인하기 위한 방문 체크용

# 연결 쌍 입력받고 그래프 생성하기
for i in range(pair):
  p1, p2 = map(int, input().split())
  computer[p1].append(p2)
  computer[p2].append(p1)

# 처음 시작한 컴퓨터에 연결되어있는 컴퓨터들을 찾아야하므로 넓이우선탐색 적용
def bfs(start):
  result = 0
  queue = deque()
  queue.append(start)

  while queue:
    x = queue.popleft()
    visited[x] = 1
    for i in computer[x]:
      if not visited[i]:
        queue.append(i)
  
  for i in visited:
    if i:
      result += 1
  return result-1

print(bfs(1))

접근

처음 시작한 컴퓨터로부터 연결되어있는 노드들을 타고 갈 수 있는 최대한 멀리 가야하므로 넓이 우선 탐색 (BFS) 사용함.
처음 시작 노드를 큐에 넣고 큐에서 뺀 후에 방문 표시를 해준다.
큐에서 뺀 노드에 연결되어있는 노드들 중 아직 방문하지 않은 노드들을 큐에 넣는다.
큐가 빌 때 까지 반복한다.
방문하지 않은 노드는 시작 노드로부터 갈 수 없는 노드이기 때문에 바이러스에 감염되지 않은 노드이므로 마지막에 방문한 노드만 카운트한다.