8장과 9장은 각각 DFS, BFS에 대한 문제들이다.
생각보다 많이 헤맸던 챕터였기 때문에, 처음부터 이론에 대한 공부를 다시 하느라 시간이 많이 걸렸다. 다행히 이론을 다시 공부하고나니, 문제들이 이해되기 시작했다...!
헷갈리는 DFS, BFS 개념을 정리해보자.
순회알고리즘
순회알고리즘이란, 그래프와 트리에 저장된 모든 값을 중복이나, 빠짐없이 살펴보고싶을 때 사용한다.
순회 알고리즘에는 DFS, BFS가 있다. 가장 먼저 DFS의 순회방법은 전위순회, 중위순회, 후위순회가 있다. 다음으로 BFS의 순회방법은 레벨순회이다. 각각에 대해 더 자세히 알아보자!
DFS(Depth First Search, 깊이우선탐색)
개념
- DFS는 뒤에서 살펴볼 BFS와 같이, 맹목적으로 각 노드를 탐색할 때 사용한다.
- BFS는 큐를 사용하지만, DFS는 스택을 사용한다.
여기서, 컴퓨터는 구조적으로 항상 스택의 원리를 사용하기 때문에(스택 프레임), 따로 스택을 사용하지 않고 재귀로도 구현이 가능하다. 재귀가 스택의 자료구조 원리를 사용하기 때문에 가능한 일이다. 보통 DFS는 재귀로 구현하는 경우가 많다. - 트리순회(전위순회, 중위순회, 후위순회-루트노드의 위치에 따라 이름이 붙혀짐)는 모두 DFS의 한 종류이다.
여기서 트리순회란, 트리구조에서 각각의 노드를 정확히 한번만, 체계적인 방법으로 방문하는 과정이다. - DFS는 모든 노드를 방문해야할 때 사용한다.
- BFS보다 구현은 간단하지만, 느리다.
알고리즘
*시작노드를 스택에 삽입하며 시작한다(DFS는 주로 전위순회로 구현) + 동시에 방문처리 해준다. (이후 아래과정 반복)
(1) 스택의 최상단 노드를 확인한다.
(2-1) 최상단 노드에게 방문하지 않은 노드가 있으면 그 노드를 스택에 넣고 방문처리한다.
(2-2) 최상단 노드에게 방문하지 않은 인접노드가 없으면 스택에서 최상단 노드를 뺀다.
위 과정이 이해되지 않는다면, 링크나 아이패드에 녹화해놓은 영상을 다시 보자!
과정참고
BFS(Breadth First Search, 너비우선탐색)
개념
- 탐색을 할 때 너비를 우선으로 탐색한다. 즉 가까운 것 위주로 탐색한다. 이러한 특징때문에, '최단경로'를 찾는 문제에서 주로 사용된다.(ex. 미로찾기)
- 큐를 사용한다(FIFO)
- DFS와 같이, 맹목적인 탐색을 할 때 사용된다. (그래프, 트리 내 모든 노드를 방문하고 싶을 때, 찾는것을 발견할 때까지 모든 노드를 적어도 한번은 방문하고 싶을 때 사용한다.)
- 레벨순회(깊이가 1인노드>2>3... 더이상 방문할 곳 없으면 탐색 마침)
알고리즘
*시작노드를 큐에 삽입하며 시작 + 방문처리 (이후 아래과정 반복)
(1) 큐에서 하나의 노드를 꺼낸다.
(2) 해당 노드에 연결된 노드 중, 방문하지 않은 노드를 방문하고 차례대로 큐에 삽입 후 방문처리한다.
위 과정이 이해되지 않는다면, 링크나 아이패드에 녹화해놓은 영상을 다시 보자!
과정참고
내가 짱이다 😎 매일 조금씩 성장하기🌱