250123 알고리즘(복습완료)

일반적인 그래프에 적용할 수 있는 BFS 탐색에는
꼭 이미 방문한 노드에 대한 스킵이 있어야 함

from collections import deque

def bfs(graph, root):
	queue = deque()
	queue.append(root)

	visited_node =[]
	while queue:
		node = queue.popleft()
		visited_node.append(node)
		for i in graph[node]:
			if i not in visited_node:
				queue.append(i)
		
	for i in visited_node:
		print(i,end=' ')
		

graph = {
    1 : [2, 3],
    2 : [1, 4],
    3 : [1],
    4 : [2]
}

bfs(graph, 1)

# 출력
# 1 2 3 4