활동일시 : 7일차 2023-08-17 21:30-23:30
목표
python으로 백준 실버5 티어 이상의 알고리즘 문제 풀기
문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
코드
python
from collections import deque
N = int(input())
C = int(input())
graph_list = {}
for i in range(C):
a, b = map(int, input().split(' '))
if a in graph_list:
graph_list[a].add(b)
else:
graph_list[a] = {b}
if b in graph_list:
graph_list[b].add(a)
else:
graph_list[b] = {a}
root_node = 1
def bfs(graph, root):
visited = set() # 방문한 노드 집합으로 변경
queue = deque([root])
while queue:
n = queue.popleft()
if n not in visited:
visited.add(n) # 방문한 노드 집합에 추가
if n in graph:
queue.extend(graph[n] - visited) # 차집합 연산을 통해 이미 방문한 노드는 큐에 추가하지 않도록 함
return visited
result = bfs(graph_list, root_node)
print(len(result) - 1) #1번 컴퓨터 제외
풀이
첫번째 컴퓨터를 통해 감염된 컴퓨터의 수를 계산하기 위해, bfs를 이용하여 연결된 컴퓨터의 수를 계산한다.
- 연결된 두 컴퓨터의 번호 a,b를 입력 받아서 딕셔너리에 연결관계를 추가한다.
1-1. 이미a번째 컴퓨터의 연결 관계가 존재할 경우 a컴퓨터와 b컴퓨터를 연결한다.
1-2. a번째 컴퓨터가 새로운 컴퓨터일 경우, a컴퓨터의 연결관계를 생성하고 b컴퓨터와 연결한다.
1-3. b도 a와 같은 방식으로 연결해준다. - 너비우선탐색(bfs)를 통해 감염 컴퓨 수를 계산한다.
2-1. 방문한 노드를 저장하기 위하여 중복이 방지되는 집합(set)을 생성한다.
2-2. 시작 노드(1)를 큐에 추가한다.
2-3. 큐의 가장 첫번째 노드를 꺼낸다.
2-4. 해당 노드가 아직 방문되지 않았을 경우엔 방문한 노드를 집합에 추가하고, 해당 노드와 연결된 노드 중 방문되지 않은 노드들을 큐에 추가한다.
느낀점
너비우선탐색 알고리즘이 뭔지 모른채로 여러번 시도했다가 매번 틀렸었던 문제이다.
결국 답답해서 너비우선탐색이 뭔지, 구현은 어떻게 하는지 공부한 다음 문제를 풀었다.
다음에는 깊이우선탐색 알고리즘을 공부하고 관련 문제를 풀어보아야겠다.
