[백준] 2606 바이러스 - 파이썬(그래프 탐색)
문제링크
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍
www.acmicpc.net
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을 빼주면 값이 나온다.
