백준 - 바이러스[2606] (DFS/BFS)
이번 포스팅에서는 백준 알고리즘의 바이러스[2606](DFS/BFS) 코딩테스트 연습 문제를 풀어봅니다.
문제 설명
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자. 1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다. 하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
| 입력 | 출력 |
|---|---|
|
7 6 1 2 2 3 1 5 5 2 5 6 4 7 |
4 |
문제 풀이
DFS, BFS 둘중 어느 탐색 방법을 사용하여도 되지만 감염되는 사항에 맞게 BFS로 문제를 풀이 하였습니다.
- 첫번째 입력은 사용하지 않습니다. 두번째 입력의 숫자 만큼 반복하여 연결된 두개의 숫자를 입력 받습니다.
- 연결된 네트워크는 방향성이 없음으로 딕셔너리 키에 컴퓨터 번호를 넣고 값에 연결된 컴퓨터 리스트를 추가합니다.
- 컴퓨터수 만큼 탐색여부를 확인 하는 딕셔너리를 추가합니다 초기 값은 모두 False로 지정합니다.
- BFS 탐색을 위한 dequelist를 생성 합니다.
- 1번 컴퓨터 부터 바이러스 감염이 시작됨으로 초기값은 1을 dequelist에 추가합니다.
- 루프를 돌리며 모든 컴퓨터를 탐색 할때 까지 루프를 반복 합니다.
- 만일 dequelist에 추가된 값이 없다면 감염되지 않는 컴퓨터중 감염된 컴퓨터와 네트워크에 연결된 컴퓨터가 존재 하지 않는 것 임으로 루프를 종료합니다.
- BFS탐색 방식으로 dequelist에서 가장 먼저 등록된 컴퓨터를 pop합니다.
- 만일 해당 컴퓨터가 이미 감염된 컴퓨터 이면 다음 루프를 진행합니다.
- 만일 해당 컴퓨터가 감염된 컴퓨터가 아니면 감염이 진행된 것으로 여기고 카운트를 증가합니다.
- 탐색여부를 확인하는 딕셔너리의 해당 컴퓨터를 True(완료된 값)로 지정합니다.
- 해당 컴퓨터와 연결된 컴퓨터의 리스트를 dquelist에 추가하여 탐색(감염)이 지속 되게 합니다.
- 최종 카운트시 초기 1번 컴퓨터 수는 제외합니다.
from collections import deque
# 입력
_ = input()
n = int(input())
lineDic = {}
for i in range(n): # 연결된 수 만큼 딕셔너리 추가
p1, p2 = map(int, input().split())
try: lineDic[p1].append(p2)
except: lineDic[p1] = [p2]
try: lineDic[p2].append(p1)
except: lineDic[p2] = [p1]
count = 0
searchDic = dict.fromkeys(lineDic.keys(), False) # 정점의 개수 만큼 탐색 여부 딕셔너리 추가
dequelist = deque() # 탐색을 위한 deque 리스트
dequelist.append(1) # 첫 탐색 시 시작정점을 추가
while not all(searchDic.values()): # searchDic의 모든 요소가 True일때 까지 반복
if len(dequelist) == 0: # 연결이 끊어져서 더이상 확인 할 영역이 없다면
break
now = dequelist.popleft() # bfs 방식 탐색
if searchDic[now]:
continue
count += 1 # 감염된 컴퓨터 수 증가
searchDic[now] = True # 현재 정점은 탐색 완료된 값으로 변경
dequelist.extend(lineDic[now])
print(count-1)
[입력]
7
6
1 2
2 3
1 5
5 2
5 6
4 7
[결과]
4
결과는 아래와 같이 잘 통과 되는 것을 확인 할 수 있습니다.
