2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
예제 입력 1 복사
7
6
1 2
2 3
1 5
5 2
5 6
4 7
예제 출력 1 복사
4
풀이
- BFS를 통해 연결된 버텍스만 방문
1. 인접리스트 생성
for문을 이용해서 vertex와 edge가 연결된 인접 리스트 생성
#1. 인접리스트 생성
for _ in range(edge_n) :
vertex, edge = map(int, input().split())
graph[vertex].append(edge)
graph[edge].append(vertex)
2. BFS 실행
2-1. 큐에 시작지점 넣기 and 재방문을 하지 않기 위해서 시작값 방문 처리
def BFS(start) :
visited[start] = True
dq.append(start)
2-2. 인접 노드 방문
2-2-1. 큐의 맨 앞에 있는거 뽑음(현재 값이 되고)
2-2-2. 현재 값에 연결된 목록들 노드들을 방문
2-2-3. 재방문 하지 않도록 방문처리
while dq :
now_idx = dq.popleft()
for i in range(len(graph[now_idx])) :
next_idx = graph[now_idx][i]
if visited[next_idx] is False : #방문하지 않았다면
visited[next_idx] = True #방문처리
dq.append(next_idx)
복습(2022.07.25)
import sys
from collections import deque
sys.stdin = open("20220725_백준_2606_바이러스.txt", "r")
def BFS(start) :
count = 0 #방문 한 곳 카운트
#1. 시작점 큐에 넣기
dq.append(start)
#2. 시작점 방문처리
visited[start] = True
#3. while dq 돌면서 한개씩 뽑으면서 방문하지 않은 곳 방문하기
while dq :
now = dq.popleft()
#한개의 노드를 방문하면서, 그 노드에 연결되어 있는 다음 노드를 또 방문한다.
#방문할때는 visited를 체크하면서, 방문하지 않은 경우에만 방문한다.
for next in graph[now] : #graph[now]는 이차원 리스트 중 한개
if visited[next] is False :
dq.append(next)
visited[next] = True
count += 1 #4. 큐로 뽑아서 방문하게 되는 경우 카운트 증가
return count
node_cnt = int(input()) #노드 개수
line_cnt = int(input()) #라인 개수
graph = [[] for _ in range(node_cnt + 1)]
visited = [False] * (node_cnt + 1)
dq = deque()
#1. 연결 사항을 확인해주는 인접 리스트 생성
for _ in range(line_cnt) :
node, line = map(int, input().split())
graph[node].append(line)
graph[line].append(node)
#2. 시작점이 1이니 1부터 BFS 탐색을 시작한다.
print(BFS(1))
전체 코드
from collections import deque
vertex_n = int(input())
edge_n = int(input())
graph = [[] for _ in range(vertex_n + 1)]
visited = [False] * (vertex_n + 1)
dq = deque()
#BFS로 연결된 버텍스 방문
def BFS(start) :
count = 0
visited[start] = True
dq.append(start)
while dq :
now_idx = dq.popleft()
count += 1
for i in range(len(graph[now_idx])) :
next_idx = graph[now_idx][i]
if visited[next_idx] is False : #방문하지 않았다면
visited[next_idx] = True #방문처리
dq.append(next_idx)
return count
#1. 인접리스트 생성
for _ in range(edge_n) :
vertex, edge = map(int, input().split())
graph[vertex].append(edge)
graph[edge].append(vertex)
print(BFS(1)-1) #방문노드 - 1번노드