반응형
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
알고리즘 분류
- 그래프 이론
- 그래프 탐색
- 너비 우선 탐색
- 깊이 우선 탐색
SOLUTION
import sys
from collections import deque
def main():
computer = {}
visit = []
for i in range(int(sys.stdin.readline())):
computer[i+1] = []
for j in range(int(sys.stdin.readline())):
num1, num2 = map(int, sys.stdin.readline().split())
computer[num1].append(num2) # 양 방향이므로 입력받은 num1, num2 서로 연결
computer[num2].append(num1) # 양 방향이므로 입력받은 num2, num1 서로 연결
queue = deque([1])
while queue:
current = queue.popleft()
if current not in visit:
visit.append(current)
for num in computer[current]:
queue.append(num)
print(len(visit)-1)
if __name__ == "__main__":
main()
'코딩테스트 대비 > BOJ' 카테고리의 다른 글
[Baekjoon/Python] 9095번: 1, 2, 3 더하기 - 효과는 굉장했다! (0) | 2021.11.12 |
---|---|
[Baekjoon/Python] 2630번: 색종이 만들기 - 효과는 굉장했다! (0) | 2021.11.12 |
[Baekjoon/Python] 1463번: 1로 만들기 - 효과는 굉장했다! (0) | 2021.11.12 |
[Baekjoon/Python] 17626번: Four Squares - 효과는 굉장했다! (0) | 2021.11.09 |
[Baekjoon/Python] 17219번: 비밀번호 찾기 - 효과는 굉장했다! (0) | 2021.11.09 |