알고리즘 분류: 그래프 이론, 그래프 탐색
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
예제 입출력
접근
문제에 네트워크를 그래프 형태로 예시를 들어주었다.
보통 네트워크에서 pc(뿐만아니라 스위치 같은 네트워크장비도 포함)를 노드라고 표현한다.
이 문제의 접근 아이디어는 다음과 같다.
- 주어진 입력으로 그래프를 만든다.
- 만들어진 그래프에서 시작노드를 1로 해서(1번이 바이러스가 걸림) bfs 탐색을 한다.
- 탐색이 끝나면 연결되어 있는 노드들은 전부 방문처리가 된다.
- 방문처리가 된 노드들이 1번에서 갈수 있는 노드(연결되어있는 노드)이므로 바이러스에 영향을 받는다.
- 방문처리된 개수를 반환해준다.
기본적인 그래프 탐색 문제였다.
방문처리는 리스트에 False로 채우고, 노드 방문시에 True로 변환해준다.
탐색이 끝나면 True의 개수를 세고 시작노드인 1번 노드는 빼야되니 -1을 해주고 반환해준다.
import sys
from collections import deque
#총 노드 수
node_num = int(sys.stdin.readline())
#그래프 만들기 - 0번은 안쓰기 위해 node_num+1
graph = [[] for _ in range(node_num+1)]
#간선 수
n = int(sys.stdin.readline())
for _ in range(n):
a,b = map(int,sys.stdin.readline().split())
graph[a].append(b)
graph[b].append(a)
#bfs함수
def bfs(start_node,graph):
#방문 체크할 노드 - 이 또한 0번째를 안씀
visited = [False for _ in range(len(graph))]
need_visited = deque(list())
need_visited.append(start_node)
while need_visited:
current_node = need_visited.popleft()
#방문을 하지 않았다면
if visited[current_node] == False:
#방문처리함
visited[current_node] = True
#다음 탐색을 위해 인접노드를 need_visited에 넣음
need_visited.extend(graph[current_node])
return visited
result = bfs(1,graph)
#True의 갯수를 세고 시작노드인 1은 빼야되니 -1을 해준다.
print(result.count(True)-1)
결과
