문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다. 한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다. 컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
입력 & 출력
- 입력 : 첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다. 이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
- 출력 : 1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
풀이
: 그래프의 연결된 모든 부분을 탐색하는 방식으로 접근하였다. DFS를 활용해서 연결된 점들을 모두 파악한다.
<풀이 단계 설정>
1. 그래프 생성
2. while을 활용하여 그래프에 연결된 점 순회
import sys
from collections import deque
PC_N = int(sys.stdin.readline())
net_N = int(sys.stdin.readline())
graph = [[] for i in range(PC_N+1)]
visited = [False for i in range(PC_N+1)]
for _ in range(net_N):
a,b = map(int,sys.stdin.readline().split(" "))
graph[a].append(b)
graph[b].append(a)
graph = [list(set(i)) for i in graph]
start = 1
q = deque([start])
visited[start] = True
while q:
v = q.popleft()
for i in graph[v]:
if not visited[i]:
q.append(i)
visited[i] = True
print(sum(visited)-1)주의) 값이 주어질 때 그래프를 잘 그려야한다. set을 이용해서 모든 점들의 연결을 넣고 중복을 제거하는 방식으로 이를 수행하였다.
풀이를 도와주었던 핵심 반례는 다음과 같다.
input:
9
8
2 3
4 5
6 7
8 9
2 5
4 7
6 9
1 8
output: 2
answer: 8느낀점 및 참고
느낀점
: DFS를 오랜만에 풀이해서 기억을 되찾는 기분이였다. 그래프 생성 시에 꼼곰하게 생성하지 못했던 부분이 아쉽고 다음 문제에서는 놓친 부분이 없는지 확인하는 습관을 길러야겠다.
