Breadth First Search (BFS) - 너비 우선 탐색

BFS 로직

1. 시작점의 인접한 정점들을 모두 차례로 방문한 후 방문했던 정점을 시작점으로 하여 다시 인접한 정점들을 차례로 방문하는 방식
2. 인접한 정점들을 탐색한 후, 차례로 너비 우선 탐색을 진행해야 하므로, 선입선출 형태의 자료구조인 Queue 활용

Queue를 사용한 알고리즘 설명

• visited list 초기화
• Q 생성
• 시작점 A를 Q에 삽입
  • visited에 A 방문 완료 표시
  • Q에서 A pop하기
  • Q에 A 인접 노드 삽입

def BFS(G, v): 					# 그래프 G, 탐색 시작점 v
	visited = [0] * n 			# n: 정점의 개수
    queue = [] 					# queue 생성
    queue.appeend(v)			# 시작점 v를 큐에 삽입
    while queue:				# queue가 비어있지 않은 경우에
    	t = queue.pop(0)		# 큐의 첫번째 원소 반환
        if not visited[t]:		# 방문되지 않은 곳이라면
        	visited[t] = True	# 방문 표시
            visit(t)
        for i in G[t]			# t와 연결된 모든 선에 대해
        	if not visited[i]	# 방문되지 않은 곳이라면
            	queue.append(i)	# 큐에 넣기

graph = {
  'A' : ['B','C'],
  'B' : ['D', 'E'],
  'C' : ['F'],
  'D' : [],
  'E' : ['F'],
  'F' : []
}

visited = [] # List to keep track of visited nodes.
queue = []     #Initialize a queue

def bfs(visited, graph, node):
  visited.append(node)
  queue.append(node)

  while queue:
    s = queue.pop(0) 
    print (s, end = " ") 

    for neighbour in graph[s]:
      if neighbour not in visited:
        visited.append(neighbour)
        queue.append(neighbour)

# Driver Code
bfs(visited, graph, 'A')

def bfs(r, c):
    visited[r][c] = 1
    q = []
    q.append((r, c))
    dr, dc = [-1, 1, 0, 0], [0, 0, -1, 1]

    while q:
        qr, qc = q.pop(0)
        for dir in range(4):
            nr = qr + dr[dir]
            nc = qc + dc[dir]
            if check(nr, nc) and visited[nr][nc] == 0:
                visited[nr][nc] = visited[qr][qc] + 1
                # 도착점에 도착했을 시
                if nr == N - 1 and nc == N - 1:
                    return
                q.append((nr, nc))