[이것이취업을위한코딩테스트다] chap05 - DFS/BFS 이론
탐색(Search) - 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정
자료구조(Data Structure) - 데이터를 표현하고 관리하고 처리하기 위한 구조
스택과 큐는 자료구조 기초 개념으로 '삽입(Push)'과 '삭제(Pop)'라는 두 핵심적인 함수로 구성된다. 또한 오버플로와 언더플로라는 데이터의 크기를 벗어난 상태에서 연산을 수행했을 때 나타나는 문제들도 고려해야 한다.
스택(Stack)
선입후출(First In Last Out)구조로, 박스처럼 먼저 들어온 데이터가 나중에 출력되는 형태이다.
위와 같이 삽입과 삭제를 반복하고, 삭제 시 가장 나중에 들어온 데이터가 삭제되는 구조이다.
python 코드로 구현 시 위와 같이 [::-1]를 통해 리스트를 뒤집어서 구현할 수 있다. append()와 pop() 메서드를 통해 뒤쪽에 데이터를 삽입하고, 뒤쪽에서 데이터를 꺼낼 수 있다.
큐(Queue)
큐는 선입선출(First In First Out)구조로 먼저 들어온 데이터가 먼저 나가는 형태이다.
이와 같이 삽입과 삭제를 반복했을 때, 먼저 들어온 데이터들이 먼저 나가는 것을 볼 수 있다.
python으로 구현했을 때, collections모듈에서 제공하는 deque 자료구조를 활용할 수 있다. deque는 데이터를 넣고 빼는 속도가 리스트 자료형에 비해 효율적이며 queue라이브러리를 이용하는 것보다 간단하다. 또한 deque객체를 리스트 자료형으로 변경하고자 한다면 list()메서드를 이용하면 된다.
재귀함수(Recursive Function)
재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다. 재귀함수에서는 언제 끝날지,종료 조건을 꼭 명시해야 한다. 함수가 무한히 호출될 수 있기 대문에, if문을 통해 종료 조건을 구현한다.
재귀함수의 대표적인 예제로 팩토리얼(Factorial)문제가 있다. 팩토리얼은 n! = 1x2x3x(n-1)xn으로 재귀함수의 형태를 가지고 있다.
위와 같이 n이 1보다 작거나 같을 때는 1을 반환하여 종료 조건을 선언하고, return을 통해 재귀적으로 함수를 호출한다. 반복문 대신에 재귀 함수를 사용했을 때 장점은 코드가 더 간결한 장점이 있다.
DFS(Depth-First Search)
DFS는 깊이 우선 탐색이라고도 부르며, 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘이다.
DFS는 스택 자료구조를 이용하며 다음과 같은 동작 과정을 가진다.
1) 탐색 시작 노드를 스택에 삽입하고 방문 처리 한다.
2) 스택의 최상단 노드에 방문하지 않은 인접 노드가 있으면 그 인접 노드를 스택에 넣고 방문 처리를 한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
다음과 같이 1에서 시작한다면, 1에서 인접한 2, 8중 작은 숫자인 2를 스택에 넣고 방문 처리한다. 그 후에 1의 인접 노드인 3으로 가는 것이 아니라, 2->7로 이동해 7을 스택에 넣고 방문 처리하는 구조이다. 즉 연결한 노드를 계속 방문하면서 탐색한다고 해서 깊이 우선 탐색이라고 한다. 결과적으로는 1->2->7->6->8->3->4->5 순서로 탐색한다.
코드로 구현하면 위와 같이 방문여부를 visited리스트로 선언하고, graph에서 해당 노드가 방문이 되지 않았다면 계속 dfs를 호출하는 재귀형태로 구현할 수 있다.
BFS(Breadth First Search)
BFS는 너비 우선 탐색이라는 의미로, 가까운 노드부터 탐색하는 알고리즘으로 다음과 같은 동작 방식을 갖는다.
1) 탐색 시작 노드를 큐에 삽입하고 방문 처리 한다.
2) 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리 한다.
3) 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.
위 사진처럼 시작 노드를 1로 주었을 때, 인접 노드인 2 3 8순서로 큐에 삽입한다. DFS와 다르게 깊이 중심으로 인접 노드를 쌓는 것이 아닌 모든 인접 노드를 큐에 삽입하고 방문 처리하는 형식을 가진다. 결과는 1->2->3->8->7->4->5->6 형태이다.
bfs를 코드로 구현하면 위와 같이 구현할 수 있다. 데이터를 담기 위한 queue를 구현하고, 큐가 빌 때까지 계속 반복하면서 연결된 원소들을 차례대로 큐에 삽입하는 형태이다.
위와 같이 DFS와 BFS는 1차원 배열이나 2차원 배열 문제에서 많이 사용된다. 각 배열의 값들이 좌표라고 생각하고, 좌표를 상하좌우로만 이동하면서 탐색을 하는 문제들이 많이 출제된다.