<BFS (Breadth First Search), 너비 우선 탐색>

• 주어지는 그래프는 이차원 행렬 또는 딕셔너리 형태일 수 있다.
• 그래프의 형태에 따라 달라질 수 있는 코드를 제공한다. 노드간의 거리, 경로를 BFS를 통해 구한다.

---

 

BFS / DFS의 기본 틀은 여러 문제에서 자주 사용된다. 익숙해지도록 외워야한다. 이번에는 input 그래프에따라 다른 BFS에 대해 코드를 보자.

 

bfs는 가까운 노드부터 탐색하며 방문한 노드의 인접한 노드들을 Queue에 넣는다.

또한 노드 방문형태로 인해 구할 수 있는 값이 있으니...

• A 노드로부터 B 노드까지의 거리를 알고 싶은 경우
• A 노드로부터 B 노드까지 가는 경로를 알고 싶은 경우

첫번째 A 노드로부터 B 노드까지의 거리를 아는 방법같은 경우를 조금 활용하면 다익스트라 알고리즘 작성에도 활용할 수 있다. (방문한 노드의 인접 노드들을 모드 Queue에 넣을 것이 아니라 비용이 최소인 애들만 넣는다면...? 한번 생각해보시길!)

 

두가지 경우에 사용 가능한 코드를 확인해보자. 큰 틀은 똑같다.

<주어진 그래프가 2D 리스트인  경우>

 

from collections import deque

#A 지점에서 B 지점까지 가는 경로를 return 한다
def bfs_path(start_x, start_y, end_x, end_y):
	rows, cols = len(graph), len(graph[0])
    
    queue = deque([(start_x, start_y, [(start_x, start_y)])])
    visited = set([(start_x, start_y)])
    
    while q:
    	curr_x, curr_y, path = queue.popleft()
        
        # end condition
        if curr_x == end_x and curr_y == end_y : 
        	return path
          
        for i in range(4):
        	nx = curr_x + dx[i]
            ny = curr_y + dy[i]

            if 0<=nx<rows and 0<=ny<cols:
            	if (nx,ny) not in visited:
            		queue.append((nx,ny,path+[(nx,ny)]))
                    visited.add((nx,ny))
 	return -1
    
# A 지점에서 B 지점까지의 거리를 return 한다
def bfs_dist(start_x, start_y, end_x, end_y, graph):
	rows, cols = len(graph), len(graph[0])
    
    queue = deque([(start_x, start_y, 1)]]
    visited = set([(start_x, start_y)])
    
    while queue:
    	curr_x, curr_y, dist = queue.popleft()
        
        if curr_x == end_x and curr_y == end_y:
        	return dist
        
        for i in range(4):
        	nx = curr_x + dx[i]
            ny = curr_y + dy[i]
            
            if 0<= nx < rows and 0<= ny < cols:
            	if (nx, ny) not in visited:
					queue.append((nx,ny,dist+1))
                    visited.add((nx,ny))
                    
	return -1
                
 # m * n 사이즈의 그래프가 들어왔다고 가정하자
 graph = [[i for i in range(n)] for _ in range(m)]
 
 dx = [-1, 1, 0, 0]
 dy = [0, 0, -1, 1]

 

<주어진 그래프가 dictionary 형태인 경우>

 

from collections import deque

def bfs_path(start_node, end_node, graph):
    queue = deque([start_node])
    visited = set([start_node])
    path = {start_node : [start_node]}
    
    while queue:        
       curr_node = queue.popleft()
       
       if curr_node == end_node:
           return path[curr_node]
       
       for next_node in graph[curr_node]:
            if next_node not in visited:
                queue.append(next_node)
                visited.add(next_node)
                path[next_node]= path[curr_node] + path[next_node]
    
    return -1


def bfs_dist(start_node,end_node, graph):
    queue = deque([start_node])
    visited = set([start_node])
    dist = {start_node : 0}
    
    while queue:
        curr_node = queue.popleft()
        
        if curr_node == end_node:
            return dist[curr_node]
        
        for next_node in graph[curr_node]:
            if next_node not in visited:
                queue.append(next_node)
                visited.add(next_node)
                dist[next_node] = dist[curr_node] + 1
                
    return -1