Ch.05 DFS/BFS

본 포스팅은 '이것이 취업을 위한 코딩테스트다!with Python (나동빈 저)'를 읽고 정리한 포스트입니다.

7월 초, 방학을 맞아 과 동기분이랑 알고리즘 스터디를 시작했다.

1학기 자료구조 과목으로 매주 머리 깨지면서 '방학 때는 좀 공부좀 해야겠다'를 뼈저리게 느꼈기 때문에.... 열심히 해보고자 한다.

꼭 필요한 자료구조 기초

• 탐색 : 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정.
  그래프, 트리 등의 자료구조안에서 탐색을 하는 문제를 주로 다룬다.
  
  
• 자료구조: 데이터를 표현하고 처리하기 위한 구조. 이번 포스팅에서는 자료구조의 기초 개념인 스택, 큐를 다룰 예정이다.
  스택, 큐는 삽입(Push)와 삭제(Pop) 두 핵심 함수로 구성된다.
  (실제로 이용시에는 이 외에도 오버플로와 언더플로를 고민해야한다.)

---

스택(Stack)

스택은 쉽게 말해서 '설거지 쌓기'를 생각하면 편하다.
설거지를 할 때 아래에서 위로 그릇을 차곡차곡 쌓으며, 쌓인 그릇을 헹굴 때에는 가장 위에 있는 그릇부터 헹군다.
이러한 구조를 선입후출 또는 후입선출(LIFO)라고 한다.

---

큐(Queue)

큐는 '대기 줄'을 생각하면 편하다. 줄을 먼저 선 사람이 먼저 나간다.
이러한 구조를 선입선출(FIFO)라고 한다.

파이썬으로 큐를 직접 구현할 수도 있지만, 실제 코딩테스트에서는 비효율적이다.
파이썬으로는 collections모듈에서 제공하는 deque자료구조를 활용하자.

---

재귀함수 (Recursive Function)

곧 다룰 DFS,BFS를 구현하기 위해서는 재귀함수에 대한 이해가 필요하다.
재귀함수는 자기 자신을 다시 호출하는 함수를 의미한다.

재귀함수를 사용하기 위해서는 종료 조건을 꼭 추가해야 한다!
그렇지 않으면 무한재귀에 빠지게 된다. => if와 함께 break와 return을 활용하도록 하자

---

탐색 알고리즘 DFS/BFS

DFS

깊이 우선 탐색이라고도 부르며, 그래프에세서 깊은 부분을 우선적으로 탐색하는 알고리즘이다. DFS를 설명하기 전에 그래프(Graph)의 기본 구조를 알아야한다.

그래프(Graph)

노드와 간선으로 표현되며, 이 때 노드를 정점이라고도 말한다.

프로그래밍에서 그래프는 인접행렬, 인접리스트 2개 방식으로 표현한다.

• 인접행렬 : 2차원 배열로 그래프의 연결 관계를 표현하는 방식
• 인접 리스트 : 리스트로 그래프의 연결 관계를 표현하는 방식
  => 파이썬은 두 방식 모두 2차원 리스트를 이용한다.

DFS는 특정한 경로로 탐색하다가 특정한 상황에서 최대한 깊숙이 들어가서 노드를 방문한 후, 다시 돌아가 다른 경로로 탐색하는 알고리즘이다.

DFS는 스택 자료구조를 이용하며, 동작과정은 다음과 같다.

1. 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
2. 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 pop한다.
3. 2번의 과정을 더 수행할 수 없을 때까지 반복한다.

#DFS 메서드 정의
def dfs(graph,v,visited):
	#현재 노드를 방문 처리 
    visited[v]=True
    print(v,end=' ')
    #현재 노드와 연결된 다른 노드를 재귀적으로 방문
    for i in graph[v]:
    	if not visited[i]:
        	dfs(graph,i,visited)
            
#각 노드가 연결된 정보를 리스트 자료형으로 표현 (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 함수 호출
dfs(graph,1,visited)

//결과
//1 2 7 6 8 3 4 5

BFS

BFS알고리즘은 너비 우선 탐색이라는 의미를 가진다.
가까운 노드로부터 탐색하는 알고리즘임

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

너비 우선 탐색 알고리즘인 BFS는 큐 자료구조에 기초한다는 점에서 구현이 간단하다.

실제로 구현함에 있어 앞서 언급한 대로 deque라이브러리를 사용하는 것이 좋으며 탐색을 수행함에 있어 O(N)의 시간이 소요된다.

from collections import deque

# BFS 메서드 정의
def bfs(graph, start, visited):
    # 큐 구현 위해 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

# 정의된 BFS 함수 호출
bfs(graph, 1, visited)

# 출력: 1 2 3 8 7 4 5 6