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

https://www.acmicpc.net/problem/2606

2606번: 바이러스

문제 설명

해당 문제는 단순히 그래프탐색을 해서 방문 가능한 노드가 총 몇개인지 확인하는 문제였다.

나는 이전에 DFS, BFS문제를 n x n으로 취급해서 문제를 풀었으나 그렇게 하면 시간복잡도가 상당히 높아지기에 인접리스트꼴로 문제를 풀었다. 

 

from collections import deque

def bfs(graph, visit):
    q = deque()
    q.append(1)
    visit[1] = 1
    global answer

    while q:
        v = q.popleft()
        for i in iter(graph[v]):
            if visit[i] == 0:
                q.append(i)
                answer = answer+1
                visit[i] = 1
        
    return answer

def dfs(v):
    visit[v] = 1

    global answer

    for i in iter(graph[v]):
        if visit[i] == 0:
            answer = answer + 1
            dfs(i)    


numberOfComputer = int(input())
numberOfLink = int(input())
answer = 0

graph = [ [] for _ in range(numberOfComputer + 1)]
visit = [0] *(numberOfComputer+1)

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

print("======answer======")
dfs(1)
print("dfs : ", answer)

print()

bfs(graph, visit)
print("bfs : ", answer)