[백준_파이썬]2606번_바이러스

내 풀이 - BFS

바이러스라서 뭔가 사방으로 퍼져나간다고 생각하여 BFS로 풀어봄

from collections import deque
queue = deque() # deque를 사용하기 위한 선언

coms = int(input()) # 컴퓨터 수
connect = int(input()) # 연결된 쌍

graph = [[] for _ in range(coms+1)] # 인덱스 0번째 안쓸 거니까 +1해줌
# graph 정보 입력
for _ in range(connect):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

visited = [False] * (coms+1) # 노드갯수 + 1(인덱스 0안쓸거니까)

def bfs(node):

    count = 0 # 감염된 컴퓨터 갯수

    # 방문한 노드 방문처리
    visited[node] = True
    # 그 노드를 큐에 넣기
    queue.append(node)

    while queue:
        # 꺼낸 노드를 하나씩 더하기
        v = queue.popleft()
        count += 1

		# 꺼낸 노드와 연결된 노드꺼내기
        for i in graph[v]:
        	# 그 때의 노드가 방문하지 않은 노드라면
            if not visited[i]:
                queue.append(i) # 큐에 넣고,
                visited[i] = True # 방문처리하기
    print(count-1) # 1번 컴퓨터 제외

# 1번 컴퓨터 감염, 따라서 시작 노드는 1
bfs(1)

 

DFS로도 풀 수 있기에 DFS로도 풀어봄

# DFS
coms = int(input())
connect = int(input())

graph = [[] for _ in range(coms+1)]
for _ in range(connect):
    x, y = map(int, input().split())
    graph[x].append(y)
    graph[y].append(x)

visited = [0] * (coms+1)
count = 0

def dfs(node):
    visited[node] = 1
    global count 

    for i in graph[node]:
        if not visited[i]:
            count += 1
            dfs(i)

dfs(1)
print(count)

 

의문인건, 원래 BFS로 풀면 DFS보다 성능이 좋다고 했었는데, 여기서 20ms가 더 빠르다

흠,,