문제
신종 바이러스인 웜 바이러스는 네트워크를 통해 전파된다.
한 컴퓨터가 웜 바이러스에 걸리면 그 컴퓨터와 네트워크 상에서 연결되어 있는 모든 컴퓨터는 웜 바이러스에 걸리게 된다.
예를 들어 7대의 컴퓨터가 <그림 1>과 같이 네트워크 상에서 연결되어 있다고 하자.
1번 컴퓨터가 웜 바이러스에 걸리면 웜 바이러스는 2번과 5번 컴퓨터를 거쳐 3번과 6번 컴퓨터까지 전파되어 2, 3, 5, 6 네 대의 컴퓨터는 웜 바이러스에 걸리게 된다.
하지만 4번과 7번 컴퓨터는 1번 컴퓨터와 네트워크상에서 연결되어 있지 않기 때문에 영향을 받지 않는다.
어느 날 1번 컴퓨터가 웜 바이러스에 걸렸다.
컴퓨터의 수와 네트워크 상에서 서로 연결되어 있는 정보가 주어질 때,
1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 출력하는 프로그램을 작성하시오.
https://www.acmicpc.net/problem/2606
입력
첫째 줄에는 컴퓨터의 수가 주어진다.
컴퓨터의 수는 100 이하인 양의 정수이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다.
둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어진다.
이어서 그 수만큼 한 줄에 한 쌍씩 네트워크 상에서 직접 연결되어 있는 컴퓨터의 번호 쌍이 주어진다.
출력
1번 컴퓨터가 웜 바이러스에 걸렸을 때, 1번 컴퓨터를 통해 웜 바이러스에 걸리게 되는 컴퓨터의 수를 첫째 줄에 출력한다.
예제
# input
7
6
1 2
2 3
1 5
5 2
5 6
4 7
# output
4문제 풀이
DFS
N = int(input())
M = int(input())
virus = [0] * (N+1)
graph = [[] for i in range(N+1)]
for i in range(M):
a, b = map(int, input().split())
graph[a] += [b]
graph[b] += [a]
def dfs(m):
virus[m] = 1
for i in graph[m]:
if virus[i] == 0:
dfs(i)
dfs(1)
print(sum(virus) - 1)백준 예제는 아래와 같이 실행됩니다.
초기 설정
virus 리스트: [0, 0, 0, 0, 0, 0, 0, 0] (인덱스 0은 사용하지 않음)
graph 리스트: [[], [2, 5], [1, 3, 5], [2], [7], [1, 2, 6], [5], [4]]
DFS 실행
dfs(1) 호출로 시작
첫 번째 호출: dfs(1)
virus[1] = 1 -> virus 리스트: [0, 1, 0, 0, 0, 0, 0, 0]
graph[1]의 인접 노드: [2, 5]
i = 2: virus[2] == 0, 따라서 dfs(2) 호출
두 번째 호출: dfs(2)
virus[2] = 1 -> virus 리스트: [0, 1, 1, 0, 0, 0, 0, 0]
graph[2]의 인접 노드: [1, 3, 5]
i = 1: virus[1] == 1 (이미 감염됨, 넘어감)
i = 3: virus[3] == 0, 따라서 dfs(3) 호출
세 번째 호출: dfs(3)
virus[3] = 1 -> virus 리스트: [0, 1, 1, 1, 0, 0, 0, 0]
graph[3]의 인접 노드: [2]
i = 2: virus[2] == 1 (이미 감염됨, 넘어감)
dfs(3) 종료, 돌아와서 dfs(2)로 복귀
i = 5: virus[5] == 0, 따라서 dfs(5) 호출
네 번째 호출: dfs(5)
virus[5] = 1 -> virus 리스트: [0, 1, 1, 1, 0, 1, 0, 0]
graph[5]의 인접 노드: [1, 2, 6]
i = 1: virus[1] == 1 (이미 감염됨, 넘어감)
i = 2: virus[2] == 1 (이미 감염됨, 넘어감)
i = 6: virus[6] == 0, 따라서 dfs(6) 호출
다섯 번째 호출: dfs(6)
virus[6] = 1 -> virus 리스트: [0, 1, 1, 1, 0, 1, 1, 0]
graph[6]의 인접 노드: [5]
i = 5: virus[5] == 1 (이미 감염됨, 넘어감)
dfs(6) 종료, 돌아와서 dfs(5)로 복귀
dfs(5) 종료, 돌아와서 dfs(2)로 복귀
dfs(2) 종료, 돌아와서 dfs(1)로 복귀
i = 5: virus[5] == 1 (이미 감염됨, 넘어감)
dfs(1) 종료
최종 결과
virus 리스트: [0, 1, 1, 1, 0, 1, 1, 0]
바이러스에 감염된 컴퓨터 수: sum(virus) - 1 = 5 - 1 = 4
BFS
from collections import deque
N = int(input())
M = int(input())
virus = [0] * (N+1)
virus[1] = 1
graph = [[] for i in range(N+1)]
for i in range(M):
a, b = map(int, input().split())
graph[a] += [b]
graph[b] += [a]
Q = deque([1])
while Q:
c = Q.popleft()
for i in graph[c]:
if virus[i] == 0:
Q.append(i)
virus[i] = 1
print(sum(virus)-1)백준 예제는 아래와 같이 실행됩니다.
초기 상태
virus: [0, 1, 0, 0, 0, 0, 0, 0]
Q: deque([1])
첫 번째 반복: while Q
c = 1
Q: deque([])
for i in graph[1] (즉, [2, 5]):
i = 2: virus[2] == 0
Q.append(2)
virus[2] = 1 -> virus: [0, 1, 1, 0, 0, 0, 0, 0]
i = 5: virus[5] == 0
Q.append(5)
virus[5] = 1 -> virus: [0, 1, 1, 0, 0, 1, 0, 0]
두 번째 반복: while Q
c = 2
Q: deque([5])
for i in graph[2] (즉, [1, 3, 5]):
i = 1: virus[1] == 1 (이미 방문, 넘어감)
i = 3: virus[3] == 0
Q.append(3)
virus[3] = 1 -> virus: [0, 1, 1, 1, 0, 1, 0, 0]
i = 5: virus[5] == 1 (이미 방문, 넘어감)
세 번째 반복: while Q
c = 5
Q: deque([3])
for i in graph[5] (즉, [1, 2, 6]):
i = 1: virus[1] == 1 (이미 방문, 넘어감)
i = 2: virus[2] == 1 (이미 방문, 넘어감)
i = 6: virus[6] == 0
Q.append(6)
virus[6] = 1 -> virus: [0, 1, 1, 1, 0, 1, 1, 0]
네 번째 반복: while Q
c = 3
Q: deque([6])
for i in graph[3] (즉, [2]):
i = 2: virus[2] == 1 (이미 방문, 넘어감)
다섯 번째 반복: while Q
c = 6
Q: deque([])
for i in graph[6] (즉, [5]):
i = 5: virus[5] == 1 (이미 방문, 넘어감)
최종 결과
virus 리스트: [0, 1, 1, 1, 0, 1, 1, 0]
바이러스에 감염된 컴퓨터 수: sum(virus) - 1 = 5 - 1 = 4
파이썬을 독학하시는 분들에게 도움이 되길 바라며,
혹 더 좋은 방법이 있거나 오류가 있다면 편하게 말씀 부탁드립니다.
