알고리즘/백준
백준 2606: 바이러스 (Python)
sssbin
2022. 1. 29. 14:30
https://www.acmicpc.net/problem/2606
2606번: 바이러스
첫째 줄에는 컴퓨터의 수가 주어진다. 컴퓨터의 수는 100 이하이고 각 컴퓨터에는 1번 부터 차례대로 번호가 매겨진다. 둘째 줄에는 네트워크 상에서 직접 연결되어 있는 컴퓨터 쌍의 수가 주어
www.acmicpc.net
bfs 먼저 풀고 dfs 풀었다
# bfs
from collections import deque
n = int(input())
m = int(input())
com = [[] for _ in range(n+1)]
for i in range(m):
data = input().split()
com[int(data[0])].append(int(data[1]))
com[int(data[1])].append(int(data[0]))
def bfs(v):
count = 0
visited = [False] * (n+1)
queue = deque([v])
visited[v] = True
while queue:
q = queue.popleft()
visited[q] = True
count += 1
for i in com[q]:
if not visited[i]:
queue.append(i)
visited[i] = True
return count-1
print(bfs(1))# dfs
n = int(input())
m = int(input())
com = [[] for _ in range(n+1)]
for i in range(m):
d1, d2 = map(int, input().split())
com[d1].append(d2)
com[d2].append(d1)
visited = [0] * (n+1)
def dfs(v):
visited[v] = 1
for i in com[v]:
if visited[i] == 0:
dfs(i)
dfs(1)
print(sum(visited)-1)
bfs -> dfs 풀면서 코드가 좀더 간결해지고 시간이랑 메모리를 줄일 수 있는 방안으로 생각해보게 됨.
