탐색 알고리즘 DFS / BFS - BFS

필요 사전 개념

노드에 대한 개념이 없다면 아래 글을 참고하자

그래프 노드로 표현하기 - 파이썬(Python)

 

 

BFS를 코드 구현하는데 필요한 deque함수의 특징을 알고 어떨 때 deque함수를 사용하는지 아래 글을 참고하자

deque 함수 활용법 - 파이썬(Python)

 

탐색 알고리즘 DFS / BFS - 파이썬(Python)

 앞서 DFS에 대해 작성한 글에 이어 BFS에 대해 알아보자

 

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

기본 원리 및 동작

• 가까운 노드부터 탐색하는 알고리즘
• 같은 level 에 있는 것부터 탐색
• 이미지 적으로는 수평적인 방향으로(동일 레벨을 기준으로 먼저 탐색) 탐색을 하는 과정

위 이미지의 숫자 순서대로 탐색

Queue 구조 (선입선출)을 사용하여 BFS를 구현

1. 탐색 시작 노드를 큐에 삽입 & 방문 처리
2. 큐에서 노드를 꺼낸다 → 인접 노드들 중에서 방문을 했는지 안 했는지 판단 → 방문하지 않았으면 큐에 넣어서 방문을 하도록 함
3. 2번의 과정을 방문을 해야할 곳이 없을 때 까지 실행

 

BFS 코드 구현

graph = {
    "1" : ["2","3","8"],
    "2" : ["1","7"],
    "3" : ["4","5"],
    "4" : ["3","5"],
    "5" : ["3","4"],
    "6" : ["7"],
    "7" : ["2","6","8"],
    "8" : ["1","7"]
}	# 위 노드를 딕셔너리로 만듬

## 만약 노드가 0으로 시작 할 경우 맨 앞에 {"0" : []}을 임의로 만들어도 동일하게 가능함

from collections import deque # deque 패키지(속도가 빠른 리스트라고 생각하자)

# 입력 : 지도, 시작점
# 기능 : DFS방식으로 주어진 지도를 탐색/방문
# 출력 : 방문한 기록을 제출

def bfs_deque( graph, start):
	# 초기 변수들에 대한 세팅
    need_visit = deque( [] ) # list() 방문할 곳 리스트 (To Do List)
    visited    = deque( [])  # list() 방문한 곳 리스트 (Done List)
    need_visit.append( start ) # 처음 출발점을 방문할 곳에 추가
    # 출발
    while need_visit:	# need_visit 할 목록이 없을 때 까지
    	# 1) 방문할 곳을 맨 앞에서 꺼냄 (Queue)
        node = need_visit.popleft()
        # node = need_visit.pop(0) # 위 코드와 같은 역할을 하지만 속도차이가 큼
        
        # 2) node 내가 이미 갔던 곳인지 체크
        #    ==> 갔던 곳이면 pass
        #    ==> 신규 방문 : (Done List) 리스트에 추가
        #                    + 이 곳에서 연결된 곳들을 받아서
        #                      (To Do List) 리스트에 추가를 해야함
        if node not in visited:	# <- 신규 방문지
        	# 2-1) (Done List) 리스트에 추가
            visited.append(node)
            # 2-2) 연결된 도시 (To Do List) 리스트에 추가
            need_visit.extend( graph[node] )
    return visited
    
bfs_deque( graph, "1")	# 위에서 설정한 graph를 지금 만든 함수에 넣어보자

deque(['1', '2', '3', '8', '7', '4', '5', '6'])    # 출력값

 

 

DFS vs BFS

DFS: 현재 정점에서 갈 수 있는 점들까지 들어가면서 탐색

BFS: 현재 정점에서 연결된 가까운 점들부터 탐색

 

코테 상황별 접근 방법

1. 그래프의 모든 점을 다 방문을 해야하는 문제 : 둘 다 가능하지만 비교적 속도에서 장점이 있는 BFS를 사용해도 좋음
2. 경로의 특징을 저장하면서 해야하는 문제 : DFS ( 일정한 경로에 대해 이어서 연속적으로 탐색을 하는 것은 DFS임)
3. 최단거리를 구해야 하는 문제 : BFS ( DFS로 경로를 검색할 경우에는 처음에 나타나는 해답이 최단거리가 아닐 수 있지만, BFS는 현재 노드에서 가까운 곳 부터 찾기 때문에 경로를 탐색 시 먼저 찾아지는 해답이 최단거리가 되는 장점이 있음)

 

연습문제

2178번: 미로 탐색

 

18352번: 특정 거리의 도시 찾기