2022.01.06

백준 2606 바이러스

## 2606
from collections import deque

N = int(input())
C = int(input())
arr = [[] for i in range(N+1)]        # N+1 해준 이유는 숫자 인덱싱을 맞추려고

for i in range(C):
    a, b = map(int,input().split())
    arr[a].append(b)
    arr[b].append(a)

visited = []        # 방문한 컴퓨터 번호
def BFS(x):
    queue = deque([x])
    visited.append(x)
    
    while queue:
        v = queue.popleft()
        for i in arr[v]:
            if i not in visited:
                queue.append(i)
                visited.append(i)
                
BFS(1)
print(len(visited) -1) # 1번 컴퓨터는 제외

queue는 while 문이 핵심 같다.popleft를 통해서 나온 수를 인덱스로 사용해서 큐에 다시 삽입하고

다시 반복을 통해서 queue를 공백으로 만드는 것이 재귀를 이용하는 DFS와의 차이처럼 느껴진다.

2021.12.29

백준 2606 바이러스

#2606

F = int(input())
C = int(input())
W = [[] for i in range(F+1)]

for i in range(C):
    a,b = map(int, input().split())
    W[a].append(b)
    W[b].append(a)

arr = []
def DFS(x):
    arr.append(x)
    for i in W[x]:
        if i not in arr:
            DFS(i)
DFS(1)    
print(len(arr)-1)            # 1을 제외 갯수를 세어야 하기 때문     

DFS 함수를 정의하는데 조금 문제가 있었다.

처음에는 return을 사용해서 재귀적으로 만들려고 했는데

오류가 뜨거나 값이 제대로 안 나오거나 그랬는데

return 할 값이 없어서 그런 듯하다.