dfs 와 bfs 에 대해 알아보기 전에
- 스택 자료구조
먼저 들어온 데이터가 나중에 나가는 형식(선입후출)의 자료구조이다.
입구와 출구가 동일한 형태로 스택을 시각화 가능.
구현 예시
- 큐 자료구조
먼저 들어온 대이터가 먼저 나가는 형식(선입선출)FIFO 의 자료구조이다.
큐는 입구와 출구가 모두 뚫려 있는 터널과 같은 형태로 시각화 가능.
구현 예시
- 재귀함수
재귀함수란 자기 자신을 다시 호출하는 함수를 의미한다.
구현 예시
최대공약수 계산(유클리드 호제법)
- 유클리드 호제법
두 자연수 a,b에 대하여 (a>b)a를 b로 나눈 나머지를 r이라고 했을때
이때 a와 b의 최대공약수는 b와 r의 최대공약수가 같습니다
유클리드 호제법의 아이디어를 그대로 재귀함수에 적용 가능
예시)
이를 코드로 구현하면
와 같은것을 알수있다.
DFS(깊이우선탐색)
dfs는 그래프에서 깊은 부분을 우선적으로 탐색하는 알고리즘 이다.
dfs는 스택 자료구조(혹은 재귀함수)를 이용하며
- 구체적인 동작과정은 다음과 같다.
- 탐색 시작 노드를 스택에 삽입하고 방문 처리를 한다.
- 스택의 최상단 노드에 방문하지 않은 인접한 노드가 하나라도 있으면 그 노드를 스택에 넣고 방문 처리한다. 방문하지 않은 인접 노드가 없으면 스택에서 최상단 노드를 꺼낸다.
- 2번 과정을 수행할 수 없을 때까지 반복.
재귀 함수를 이용한 dfs 예시이다.
BFS(너비 우선 탐색)
그래프에서 가까운 노드부터 우선적으로 탐색하는 알고리즘 이다.
BFS는 큐 자료구조를 이용하며
- 구체적인 동작 과정은 다음과 같습니다.
- 탐색 시작 노드를 큐에 삽입하고 방문 처리를 합니다.
- 큐에서 노드를 꺼낸 뒤에 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리합니다.
- 2번의 과정을 수행할 수 없을 때 까지 반복합니다.
:)