문제 이해
이 문제는 1번 컴퓨터로부터 시작된 바이러스가 몇개의 컴퓨터로 퍼져나가는지를 세는 문제이다.
아래의 그림에서 1번 컴퓨터와 연결되어 있는 컴퓨터는 2,3,5,6번으로 총 4개의 컴퓨터가 추가적으로 감염된다.
입력에는 총 컴퓨터의 개수, 간선의 개수, 연결된 간선이 주어진다.
출력에는 감염된 컴퓨터의 개수를 출력한다.
무조건 1번 컴퓨터로 감염이 시작된다고 가정한다.
문제 접근
BFS문제라고 볼 수 있다.
전에 풀었던 1260번 DFS와 BFS 문제와 매우 비슷하다.
문제를 풀기 위해서는 이 간선을 정리해야 하는데 간선은 2차원 배열을 통해서 정리할 수 있다.
그 후 BFS를 통해 문제를 푼다.
- 간선 정리
- BFS
문제 풀이
간선 정리
2차원 배열에 아래와 같이 넣어준다.
이렇게 넣게 되면 1번 컴퓨터에 연결된 컴퓨터들이 net[1]에 리스트로 정리되어있다.
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
net = [[] for _ in range(N+1)]
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
net[a].append(b)
net[b].append(a)
BFS
우선 이미 감염되었다면 중복으로 체크하면 안되기 때문에 visited라는 감염 체크 리스트를 만든다.
이 감염 체크 리스트에 컴퓨터의 번호를 넣고 만약 감염되지 않았지만 간선에 연결되어 있다면 감염 리스트에 추가하고 count를 증가시키는 방식이다.
이렇게 되면 초기에 1번 컴퓨터를 넣었기 때문에 1번 컴퓨터와 연결되어 있는 모든 컴퓨터들이 감염 리스트에 들어가고, 또 감염 리스트에 들어간 컴퓨터들로부터 연결된 컴퓨터들을 감염 리스트에 넣을 수 있게 된다.
visited = [False for _ in range(N+1)]
def bfs():
q = deque()
count = 0 # 감염된 컴퓨터 수
q.append(1) # 1번 컴퓨터로부터 시작
visited[1] = True # 1번 컴퓨터 감염완료
while q:
cur = q.popleft()
for i, val in enumerate(net[cur]): # 감염된 컴퓨터로부터 연결된 컴퓨터들에서
if visited[val]==False: # 감염되지 않았다면
q.append(val) # 감염리스트에 추가
visited[val] = True # 감염완료
count += 1 # 감염된 컴퓨터 수 1 증가
print(count) # 모두 감염되었을 때 출력제출 코드
import sys
from collections import deque
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
net = [[] for _ in range(N+1)]
for _ in range(M):
a, b = map(int, sys.stdin.readline().split())
net[a].append(b)
net[b].append(a)
def bfs():
q = deque()
count = 0 # 감염된 컴퓨터 수
q.append(1) # 1번 컴퓨터로부터 시작
visited[1] = True # 1번 컴퓨터 감염완료
while q:
cur = q.popleft()
for i, val in enumerate(net[cur]): # 감염된 컴퓨터로부터 연결된 컴퓨터들에서
if visited[val]==False: # 감염되지 않았다면
q.append(val) # 감염리스트에 추가
visited[val] = True # 감염완료
count += 1 # 감염된 컴퓨터 수 1 증가
print(count) # 모두 감염되었을 때 출력
visited = [False for _ in range(N+1)]
bfs()
