[python]백준 2606번: 바이러스(BFS)

# 2606 바이러스

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

2606번: 바이러스

코드

from collections import deque
n = int(input())
v = int(input())

graph = [[] for i in range(n+1)]
visited = [0] * (n+1)

for i in range(v):
  a, b = map(int, input().split())
  graph[a] += [b]
  graph[b] += [a]

visited[1] = 1
Q = deque([1])

while Q:
  C = Q.popleft()
  for nx in graph[C]:
    if visited[nx] == 0:
      Q.append(nx)
      visited[nx] = 1

print(sum(visited)-1)

📝 풀이

BFS(Breadth-First Search)란 너비 우선 탐색이라고도 불리며 그래프에서 시작 노드에 인접한 노드부터 탐색하는 알고리즘이다. BFS 알고리즘은 주로 그래프에서 모든 간선의 비용이 동일한 조건에서 최단 거리를 구하는 문제를 효과적으로 해결할 수 있는 알고리즘이다. 

 

BFS 알고리즘은 그래프에서 가까운 노드부터 우선적으로 탐색한다는 점에서 선입선출 방식의 큐(Queue) 자료구조를 활용한다. 즉, BFS는 인접한 노드를 반복적으로 큐에 삽입하고 먼저 삽입된 노드부터 차례로 큐에서 꺼내도록 알고리즘을 작성하면 된다.

 

BFS 알고리즘의 동작과정은 아래와 같다.

1. 탐색 시작 노드 정보를 큐에 삽입하고 방문 처리한다.

2. 큐에서 노드를 꺼내 방문하지 않은 인접 노드 정보를 모두 큐에 삽입하고 방문 처리한다.

3. 2번의 과정을 더 이상 수행할 수 없을 때 까지 반복한다.

 

📝 코드 뜯어보기

from collections import deque
n = int(input()) # 컴퓨터 개수
v = int(input()) # 연결선 개수

graph = [[] for i in range(n+1)] # 그래프 초기화
visited = [0] * (n+1) # 방문한 컴퓨터인지 표시

for i in range(v): # 그래프 생성
  a, b = map(int, input().split())
  graph[a] += [b] # a에 b 연결
  graph[b] += [a] # b에 a 연결 양방향

# graph = [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]

n에는 컴퓨터 개수를 입력받고, v에는 연결선의 개수를 입력 받는다. n+1만큼의 반복문을 통해 graph를 생성해주고 visited를 통해 방문 여부를 확인할 수 있게 해준다. n이 아닌 n+1인 이유는 1번 컴퓨터를 1번 인덱스에 쓰기 위해 n+1로 설정해주었다. visited의 0은 방문하지 않은 상태이고, 1이면 방문한 상태이다. 연결된 연결선 수 만큼 반복문을 통해 a, b 값을 입력 받고 그래프를 연결시켜준다. 

visited[1] = 1
Q = deque([1])

while Q:
  C = Q.popleft()
  for nx in graph[C]:
    if visited[nx] == 0:
      Q.append(nx)
      visited[nx] = 1

print(sum(visited)-1)

1번 컴퓨터부터 시작이니 visited[1] = 1로 방문 표시를 하고 첫 번째 컴퓨터에 대해 덱을 만든다. Q에 값이 있는 동안에 while문이 실행될 수 있게 설정해주고 C = Q.popleft()를 통해 Q에 맨 왼쪽 값들을 빼주면서 C에 저장해준다. 반복문으로 graph[C]를 nx에 할당해주고 if visited[nx]가 방문하지 않은 곳이라면 Q에 nx값을 넣어주고 visited[nx]를 방문처리 해준다. 방문했던 모든 컴퓨터를 더해주고 시작했던 1번 컴퓨터를 제외하고 출력해준다.'

 

참고
https://heytech.tistory.com/56

[Python] BFS 알고리즘 개념 및 실습

https://bio-info.tistory.com/152

[백준] 2606 바이러스 - Python (그래프 탐색)