[백준/DFS-BFS] 2606: 바이러스 - 파이썬

문제

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

2606번: 바이러스

 

제출한 풀이

from collections import deque

n = int(input())
m = int(input())
graph = [[] for _ in range(n+1)]

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

def bfs(graph, start, visited):
    queue = deque([start])
    while queue:
        v = queue.popleft()
        
        for j in graph[v]:
            if j not in visited:
                visited.append(j)
                queue.append(j)
                
    return len(visited)-1

print(bfs(graph, 1,visited))

 

실행시간이 짧은 풀이

from sys import stdin
read = stdin.readline
dic={}
for i in range(int(read())):
    dic[i+1] = set()
for j in range(int(read())):
    a, b = map(int,read().split())
    dic[a].add(b)
    dic[b].add(a)

def bfs(start, dic):
    queue = [start]
    while queue:
        for i in dic[queue.pop()]:
            if i not in visited:
                visited.append(i)
                queue.append(i)
visited = []
bfs(1, dic)
print(len(visited)-1)

 

두번째 풀이의 실행시간이 짧았다. 그 이유는 list를 쓰지않고 set자료형을 사용하였는데

set에서의 시간복잡도는 O(1) 이고 list에서 시간복잡도는 O(n)이기 때문이다.

또한 첫번째 풀이에서 list사용과 sort()연산을 사용하여 시간이 더 오래 걸렸다.

set을 사용하면 정렬할 필요가 없고 시간복잡도가 작기 때문에 list 사용보다 set, deque 사용이 파이썬에서 더 바람직함

 

파이썬 list, deque, set 시간복잡도는 여기서 확인할 수 있음