BFS

개념

시작 정점을 방문한 후 시작 정점에 인접한 모든 정점들을 우선 방문하는 방법,즉 인접한 노드들부터 차례로 방문하기에 목표지점까지의 최단거리로 탐색하기 적합

관련문제

https://www.acmicpc.net/problem/2178

구현과정

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

시간복잡도

노드의 갯수를 V,간선의 갯수를 E라 할때 해당 노드만큼의 방문배열생성(V)+각 노드의 인접노드의 합(E)이므로 O(V+E)이다.

코드

#예시 그래프 배열 선언
graph = [
    [],
    [2, 3, 4],
    [1, 5, 6],
    [1],
    [1, 7],
    [2],
    [2, 8],
    [4],
    [ 6]
]
#방문기록을 위한 배열 선언
visited=[False]*len(graph)

#방문할 노드 저장을 위한 배열
list=deque()
#시작노드를 1로 설정
list.append(1)
while len(list)>=1:
    node=list.popleft()
    print(node)
    for node in graph[node]:
    	#방문하지 않았던 노드들만 추가
        if visited[node]==False:
            list.append(node)
            visited[node]=True

예시

설명

다음은 롤의 맵중의 하나인 소환사의 협곡이다.
흔히 커서로 땅을 클릭하면 자동으로 최단거리를 선으로 표시하게된다.이를 BFS알고리즘을 활용하여 경로추적을 곁들여 구현해보자.

1.전처리

(1)컬러와 흑백의 경계처리 비교

산,벽,포탑등의 구조물들은 통과할 수 없기에 따로 1이나 False등의 전처리를 거쳐야한다.
이를 위해 python의 opencv를 이용하여 경계선을 처리해보도록 하자.

import cv2
import matplotlib.pyplot as plt
import numpy as np
import matplotlib.animation as animation

image_path="./lol.jpg"

#경계선 한계값
threshold1=70
threshold2=120

#크기조정값
resize_height=400
resize_width=400

#사진 로드
lol=cv2.imread(image_path)
lol=cv2.cvtColor(lol,cv2.COLOR_BGR2RGB)

#크기 조정된 사진
resized_lol=cv2.resize(lol,(resize_height,resize_width))
#경계처리된 사진
edged_lol=cv2.Canny(lol,threshold1,threshold2)
#경계처리된 크기조정 사진
edged_resized_lol=cv2.Canny(resized_lol,threshold1,threshold2)

#흑백 사진 로드
lol_gray=cv2.imread(image_path, cv2.IMREAD_GRAYSCALE)

#크기조정된 흑백 사진
resized_lol_gray=cv2.resize(lol_gray,(resize_height,resize_width))
#경계처리된 흑백 사진
edged_lol_gray=cv2.Canny(lol_gray,threshold1,threshold2)
#경계처리된 크기조정 흑백 사진
edged_resized_lol_gray=cv2.Canny(resized_lol_gray,threshold1,threshold2)

plt.subplot(2,3,1)
plt.title('400x400 resized image')
plt.imshow(resized_lol)

plt.subplot(2,3,2)
plt.title('bordered image')
plt.imshow(edged_lol)

plt.subplot(2,3,3)
plt.title('400x400 resized,bordered image')
plt.imshow(edged_resized_lol)


plt.subplot(2,3,4)
plt.title('gray,400x400 resized image')
plt.imshow(resized_lol_gray,cmap="gray")

plt.subplot(2,3,5)
plt.title('gray,bordered image')
plt.imshow(edged_lol_gray,cmap="gray")

plt.subplot(2,3,6)
plt.title('gray,400x400 resized,bordered image')
plt.imshow(edged_resized_lol_gray,cmap="gray")

plt.show()

출력

opencv의 canny를 통해 경계처리를 함에 있어서 컬러사진을 경계처리했을 때와 흑백사진을 경계처리했을 때를 비교할 필요가 있다.위의 "bordered image","400x400 resized,bordered image"는 컬러사진을 경계처리 했을 때이고 "gray,bordered image"와 "gray,400x400 resized,bordered image"는 흑백사진을 경계처리 했을 경우이다.둘을 비교해 보았을 때 컬러사진의 경계처리가 더 난잡한것을 볼 수 있다.이는 부쉬나 나무들의 색이 언덕지형의 색과 비슷해 경계로 인식될 수 있기 때문이다.따라서 경계처리를 하기전에 흑백사진으로 변형하여 최대한 색감을 없애줘야한다.

(2)Canny의 threshold값 조정

cv2.Canny(gray_img, threshold1, threshold2)에서 threshold 2개를 조정 할 수 있다.
threshold2는 경계선으로 인식 될 수 있는 한계값이고 threshold1은 경계선의 인접한 연장선으로의 한계값이라고 생각하면 쉽다.(threshold1이 줄어든다면 경계선에서 뻗어나오는 선들이 많아지고 threshold2가 줄어든다면 경계선 자체가 많아진다.)여러 값들을 조정해본 결과 threshold1=70,threshold2=120이 적당한 경계선 인 것 같다.

threshold1=70,threshold2=120의 경계처리 결과

(모든 요소의 값은 0또는 255로 저장이 된다.)

2.맵에서의 bfs 알고리즘

미로탐색의 문제의 해법과 경로를 표시하기 위한 경로추적도 적용해야한다.

from collections import deque

#imread로 불러들인 이미지는 np형태이기 때문에 리스트로 변환
edged_map=edged_resized_lol_gray.tolist()
#방문기록 및 경로 추적 위한 리스트 초기화
path_map=[[False for _ in range(resize_width)] for _ in range(resize_height)]
#최소 거리저장을 위한 리스트 초기화
dis_map=[[0 for _ in range(resize_width)] for _ in range(resize_height)]

from collections import deque

def make_track_with_bfs_map(maps,path_map,dis_map,start,end):
    #시작점은 방문을 이미 한것으로 간주
    path_map[start[0]][start[1]]=True
    #기존의 상하좌우에서 대각선 방향도 추가
    x_offset=[-1,1,0,0,1,1,-1,-1]
    y_offset=[0,0,1,-1,-1,1,-1,1]
    to_do_list=deque([(*start,0)])
    cnt=0
    while len(to_do_list)>0:
        x,y,d=to_do_list.popleft()
        cnt+=1
        indexes=[(x+x_offset[i],y+y_offset[i]) for i in range(8)]
        for nx,ny in indexes:
            next_dis=round(((x-nx)**2+(y-ny)**2)**(1/2),2)
            #다음 x와 다음 y가 벽이 아니고 유효한 범위의 좌표라면
            if (0<=nx and nx<len(maps)) and (0<=ny and ny<len(maps[0])) and maps[nx][ny]==0:
                #다음 x와 다음 y가 아직 방문하지 않은 곳이나 현재 기준의 거리가 전보다 짧다면(특정 상황에서는 8칸 움직였던 거리가 7칸 움직였던 거리보다 짧을 수 있다.)
                if (path_map[nx][ny]==False) or (dis_map[nx][ny]>d+next_dis):
                    #옆의 길이 막혀있지 않을 경우(대각선 방향을 고려)
                    if (maps[x][ny]==0 or maps[nx][y]==0):
                        to_do_list.append((nx,ny,d+next_dis))
                        path_map[nx][ny]=(x,y)
                        dis_map[nx][ny]=d+next_dis
    print(cnt)
    return dis_map[end[0]][end[1]]

#경로 추적
def tracking_path(track,start,end):
    result=[]
    cur_x_y=end
    while cur_x_y!=start:
        result.append(cur_x_y)
        x,y=cur_x_y
        cur_x_y=track[x][y]
    result.append(start)

    return list(reversed(result))

#사직좌표와 목표좌표 입력
print("시작좌표:")
start=tuple(map(int,input().split()))
print("도착좌표:")
end=tuple(map(int,input().split()))

#시작좌표와 목표좌표가 유효한지 
if edged_map[start[0]][start[1]]==255 or edged_map[end[0]][end[1]]==255:
    print("유효하지 않은 좌표값입니다.")
else:
    #경로표시를 위한 RGB값(빨간색)
    rgb=[200,15,15]
    min_dis=make_track_with_bfs_map(edged_map,path_map,dis_map,start,end)

    if min_dis==0:
        print("도달 불가능",min_dis)
    else:
        print("최단 거리:",min_dis)

        # 최단거리의 경로 생성
        path=tracking_path(path_map,start,end)

        for x,y in path:
            resized_lol[x][y]=rgb

        cv2.imwrite(f"{start}_to_{end}_path_image.jpg",cv2.cvtColor(resized_lol,cv2.COLOR_RGB2BGR))

3.입력 및 확인

• 메모장을 통해 픽셀 좌표를 확인하는데 이때 입력해야는 x,y가 메모장의 좌표와 순서가 바뀌어 있음을 인지해야한다.(픽셀좌표가 10,20이라면 입력해야하는 좌표는 20,10이다.)

330 90
260 260

위처럼 빨간색의 경로가 입혀져 있음을 확인 할 수 있다.

4.한계점

• 기존의 거리보다 짧으면 갱신하며 노드를 추가하기 때문에 같은 노드를 여러번 방문할 수 있어 상하좌우만 따지는 보편적인 bfs보다 오래걸린다.
• 벽이나 산같은 지형의 완전한 전처리가 필요하다.(중간중간 뚫려있는 곳도 존재)
• 시작점과 도착점의 모든 경우의 수를 미리 계산 후 각 해쉬에 데이터를 넣어두면 빠르게 최단경로를 보여줄 수 있다.(속도를 위해 메모리를 포기)