BFS

# BFS - 깊이 우선 탐색

from collections import deque


def make_graph(node, edge):
    graph = [[] for _ in range(node + 1)]
    for _ in range(edge):
        n, m = map(int, input().split())
        graph[n].append(m)
        # 무방향 그래프일 때
        graph[m].append(n)
    for i in range(len(graph)):
        graph[i].sort()

    return graph


def BFS(graph, queue, visited):
    while len(queue) != 0:
        e = queue.popleft()
        if e not in visited:
            visited.append(e)
        for i in graph[e]:
            if i not in visited:
                queue.append(i)


N, E = map(int, input().split())
G = make_graph(N, E)
Q = deque([1])
V = []

BFS(G, Q, V)
print(V)

 

어제 DFS를 구현해보니 BFS는 조금 수월하게 만들었다.

근데 not in 을 쓰면 효율이 떨어지진 않을까 생각이 든다.

---

효율이 떨어진다. 

https://twpower.github.io/120-python-in-operator-time-complexity

[Python] 파이썬 'in' 연산자 시간 복잡도(Time Complexity)

in 시간 복잡도가 O(n) 이기 때문에 불필요하게 연산을 많이 하게 된다.

BFS, DFS 모두 시간복잡도를 고려해서 다시 짜봐야겠다.