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

문제링크

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

2606번: 바이러스

 

from collections import deque
import sys

n = int(sys.stdin.readline()) //컴퓨터의 갯수
l = int(sys.stdin.readline()) //연결선의 갯수

graph = [[] for i in range(n + 1)] //연결선들의 그래프
visited = [0] * (n + 1) //방문노드

for i in range(l):
  a,b = map(int,sys.stdin.readline().split())
  graph[a] += [b]
  graph[b] += [a]
  
visited[1] = 1 //1번에서 시작하므로
q = deque()
q.append(1)

while q:
  alpha = q.popleft() 
  for nx in graph[alpha]:
    if visited[nx] == 0:
      q.append(nx)
      visited[nx] = 1
      
print(sum(visited)-1)

 

이 문제는 2447번 그래프 탐색 문제와 형식이 달랐다. 벽 때문에 막혀 못가는 형식이 아니었다.

 

전체 컴퓨터와 연결선의 갯수를 n,l 로 받아준다.

2차원 배열 graph와 방문한 위치를 표시할 수 있는 1차원 배열 visited를 선언한다.

갯수를 n+1로 받아준 것은 배열에서의 인덱스 값은 원래 값보다 1이 작으므로 편의상 n+1로 크기를 지정했다.

 

연결선의 갯수만큼 for문을 실행 시키는데 a,b 값은 단방향 연결이 아닌 쌍방향 연결이므로

graph[a] += [b], graph[b] += [a]로 값을 서로 넣어주었다.

 

1번 컴퓨터가 감염되고 시작하므로 1번의 방문 여부를 1로 체크하고 마지막 결과에서 1을 빼준다.(방문하면 1, 방문하지 않으면 0)

deque를 q로 설정한 후 1을 넣어주고 while문에서는 q의 값이 없으면 종료하도록 설정한다.

 

먼저 들어온 q의 값을 popleft()로 뺴주고 alpha로 받는다.

 

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

visited = [0,1,0,0,0,0,0,0]

q = [1] 인 상태에서 시작한다.

 

alpha가 1이면 graph에서 [2,5]의 값을 받아오므로 visited[2], visited[5]의 값이 0이었으니 1로 바꿔주고 q 값에 넣어준다.

visited = [0,1,1,0,0,1,0,0]

q = [2,5]가 된다.

 

그 다음에 2를 빼주고 alpha로 받은 후 실행해보면

visited = [0,1,1,1,0,1,0,0]

q = [5,3]

 

5를 빼주고 alpha로 받고 실행해보면

visited = [0,1,1,1,0,1,1,0]

q = [3,6]

 

3,6을 실행해보면 이미 visited의 값이 1이므로 변경사항 없이 그대로 종료된다.

visited의 합에서 처음 방문한 1을 빼주면 값이 나온다.

 

위 문제를 bfs,dfs로 실행할 때의 순서