[이코테-5] DFS/BFS(3) - BFS

 

BFS( Breadth-First Search)

BFS는 너비 우선 탐색 방식으로, 그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘이다. 특정 경로에서의 최단거리 문제를 풀 때 많이 쓰인다.

DFS는 스택 자료구조를 사용했다면, BFS는 큐를 사용하고, 구체적인 작동 방식은 다음과 같다.

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리
2. 큐에서 노드 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리
3. 더 이상 2번의 과정을 수행할 수 없을 때까지 반복함.

 

이 그래프를 이번엔 BFS 방식으로 노드들을 방문해보자.

 

1. 시작 노드인 '1'을 큐에 삽입하고 방문 처리

 

2. 큐에서 노드 '1'을 꺼내 방문하지 않은 인접 노드 '2','3','8'을 큐에 삽입하고 방문 처리 

 

같은 방법으로 그 다음은 큐에서 노드'2'를 꺼내고, 방문하지 않은 인접 노드 '7 '을 삽입하고 방문 처리한다. 그 다음은 '3'을 꺼내 방문하지 않은 인접 노드 '4','5'를 큐에 삽입하고 방문처리하고, 그 다음은 큐에서 노드'8'을 꺼내고, 인접 노드가 없으므로 다음 노드 '7'을 꺼낸다. 이 과정을 반복하면, 최종적으로 전체 노드의 탐색순서는 1-> 2-> 3-> 8-> 7 -> 4 -> 5 -> 6 이 된다.

 

소스코드 <Python>

from collections import deque #deque는 양쪽에서 삽입/삭제가 가능한 자료구조

def bfs(graph, start, visited):
	queue = dequeue([start]) #처음엔queue에 start만 들어있음
    visited[start] = True
    while queue:
    	v = queue.popleft()
        print(v, end = ' ')
        for i in graph[v]:
        	if not visited[i]:
            	queue.append(i)
                visited[i] = True
                
#graph는 주어짐. 2차원 배열 형태. 예를들어 graph의 길이가 9라고 하면

visited = [False] * 9
bfs(graph,1, visited)

 

소스코드 <JavaScript>

//bfs

function bfs(visited, start, graph){
	let queue = [start];
    	visited[start] = true;
    
	while (queue.length >0){
    	let v= queue.shift();
        process.stdout.write(v + " ");
        for (let i in graph[v]){
        	if (!visited[i]){
            	queue.push(i);
                visited[i] = true;}}}
                
            
let visited = new Array(9).fill(false);
bfs(visited, 1, graph);

 

 

<문제 예시 -- 미로탈출 >

 

 

풀이 아이디어

이 문제는 '최단거리'문제이므로, BFS를 떠올릴 수 있다.

BFS는 시작 지점에서 가까운 노드부터 차례대로 그래프의 모든 노드를 탐색한다.

상, 하, 좌, 우로 연결된 모든 노드로의 거리가 1로 동일하다.

따라서, (1,1) 지점부터 BFS를 수행하여 모든 노드의 최단 거리 값을 기록하면 해결할 수 있다.

예를들어, (1,1)에서 출발한다고 하면, 그 노드로부터 상/하/좌/우의 노드들을 확인하여 0이면 해당 노드를 방문한다.

 

from collections import deque

def bfs(x,y):
	queue = deque()
    queue.append((x,y))
    
    while queue:
    	x,y = queue.popleft()
        for i in range(4):
            nx = x + dx[i]
            ny = y + dy[i]


            if nx < 1 or ny < 1 or nx >= n or ny >= n:
                continue
            if graph[nx][ny] == 0:
            	continue
            if graph[nx][ny] == 1:
                
                graph[nx][ny] = graph[x][y] + 1
                queue.append((nx,ny))
                
    return graph[nx-1][ny-1]
    
    #입력받기
    n,m = map(int, input().split())
    graph = []
    for i in range(n):
    	graph.append(list(map(int, input().split())))
        
    dx = [-1,1,0,0]
    dy = [0,0,-1,1]
    print(dfs(0,0))