[Python] 이것이 코딩테스트다 with 파이썬 - 탐색 알고리즘 DFS/BFS - BFS(Breath-First-Search)편

* 해당 문제 및 해설은 "이것이 코딩 테스트 다 with 파이썬" 책을 기준으로 요약 및 정리 하여 작성하였습니다.  

 

http://www.yes24.com/product/goods/91433923

이것이 취업을 위한 코딩 테스트다 with 파이썬 - YES24

 

총 2편으로 나누어서 작성할 예정입니다. ( 모든 이미지는 PPT 를 활용하였습니다.)

1. DFS(Depth-First-Search) 편  
2. BFS (Breath-First-Search) 편 - 현재

---

탐색 알고리즘 DFS / BFS ★★★★★

코딩테스트 단골 손님 탐색 알고리즘 DFS / BFS

스택과 큐, 재귀함수가 DFS / BFS 의 중요한 개념이기 때문에, 모르겠고 기초부터 해야한다면 글을 읽어보길 바란다.

 

BFS

BFS 는  Breath-First Search, 너비 우선 탐색이라고도 부르며, 그래프에서 가장 가까운 부분을 우선적으로 탐색하는 알고리즘 이다.

 

• DFS 는 최대한 멀리 있는 노드를 우선으로 탐색하는 방식으로 동작한다고 했는데 BFS는 그 반대다.
• BFS 구현에서는 선입선출 방식인 큐 자료구로를 이용하는 것이 정석이다.
• 인접한 노드를 반복적으로 큐에 넣도록 알고리즘을 작성하면 자연스럽게 먼저 들어온 것이 먼저 나가게 되어,
  가까운 노드부터 탐색을 진행하게 된다.

 

BFS 알고리즘의 정확한 동작 방식은 다음과 같다.

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

 

아래 이미지를 보고 참고 하시면, 이해하기 편하실 듯 합니다.

 

단계 1  시작 노드인 '1' 을 큐에 삽입하고 방문 처리를 한다.
           방문 처리된 노드는 노란색 으로, 큐에서 꺼내 현재 처리하는 노드는 파란색 으로 표현했다.

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

단계 3  큐에서 노드 '2' 를 꺼내고 방문하지 않은 인접 노드 '7' 을 큐에 삽입하고 방문 처리를 한다.

단계 4  큐에서 노드 '3' 을 꺼내고 방문하지 않은 인접 노드 '4', '5' 를 모두 큐에 삽입하고 방문 처리를 한다.

단계 5  큐에서 노드 '8'을 꺼내고 방문하지 않은 인접 노드가 없으므로 무시한다.

단계 6  큐에서 노드 '7'을 꺼내고 방문하지 않은 인접 노드 '6'을 큐에 삽입하고 방문 처리를 한다.

단계 7  남아 있는 노드에 방문하지 않은 인접 노드가 없다.
            따라서 모든 노드를 차례대로 꺼내면 최종적으로 다음과 같다.

결과적으로 노드의 탐색 순서 (큐에 들어간 순서)는 다음과 같다.

• 1 -> 2 -> 3 -> 8 -> 7 -> 4 -> 5 -> 6

 

TIP

재귀 함수로 DFS 를 구현하면 컴퓨터 시스템의 동작 특성상 실제 프로그램의 수행 시간은 느려질 수 있다.
따라서 스택 라이브러리르 이용해 시간 복잡도를 완화하는 테크닉을 필요할 때도 있다.
다만, 코딩 테스트에서는 보통 DFS 보다는 BFS 구현이 조금 더 빠르게 동작한다는 정도는 기억하도록 하자

• 큐를 사용하기 위해, deque 라이브러리 활용하기

 

BFS 예제 코드

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
	# 큐 (Queue) 구현을 위해 deque 라이브러리를 사용
    queue = deque([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
    
 # 각 노드가 연결된 정보를 리스트 자료형으로 표현 (2차원 리스트)
 graph = [
 	[],
    [2, 3, 8],
    [1, 7],
    [1, 4, 5],
    [3, 5],
    [3, 4],
    [7],
    [2, 6, 8],
    [1, 7]
 ]
 
 # 각 노드가 방문된 정보를 리스트 자료형으로 표현(1차원 리스트)
 visited = [False] * 9
 
 # 정의된 DFS 함수 호출
 bfs(graph, 1, visited)
 
 # 출력 값
 1 2 3 8 7 4 5 6

 

DFS / BFS 간단 정리

	DFS	BFS
동작 원리	스택	큐
구현 방법	재귀 함수 이용	큐 자료구조 이용

 

코딩 테스트 중 2차원 배열에서의 탐색 문제를 만나면 그래프 형태로 바꿔서 생각하면 풀이 방법을 쉽게 떠올릴 수 있다.