[PS/탐색/BFS/DFS] 여기저기 이곳저곳 탐색탐색

#1 들어가기

알고리즘 공부의 첫번째 산. 탐색.
스터디메이트랑 열심히 머리 굴리며 탐색 예제문제를 풀었지만....결과는 처참하게 패배.
문제를 보고 DFS를 사용해야 하는지, BFS를 사용해야 하는지 감도 안올 뿐더러
문제마다 탐색 알고리즘도 조금씩 바꿔야하는데,,,,
분명 학과 커리에 있는 자료구조수업을 들으며 탐색도 같이 배웠었는데, 막상 쓰려고 하니 이게 뭔지 싶었다.
그래서 공부하며 정리해보는 글.
탐색에서 해매고 계시는 분들, 저와 함께 헤쳐나가 봅시다.

 

 

#2 자료구조

탐색을 하기 이전에, 무엇을 탐색할지를 알아야 한다.
우리가 탐색할것은 어떠한 구조로 이루어진 자료(데이터) 들 이다. 다시말하면, 요놈을 '자료구조' 라고 하는데...
자료구조는 기본형에서 시작해 여기서 파생되는 녀석들이 수도없이 많다.

이렇게 보니 한눈에 들어오긴 하는데...

학교 수업 들으며 과제를 할때, 웬만한 데이터는 다  링크드 리스트로 때려박은 기억이(...)있다.

 

#3 탐색

탐색(search)이란 많은 양의 데이터 중에서 원하는 데이터를 찾는 과정을 의미한다.
책에서 볼때는 참 쉬워보이는데, 막상 구현해보려고 하면 왜 안되는지 정말 모르겠는 녀석.

대표적인 탐색 알고리즘엔 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 이 있다.
둘 다 간선을 통해 노드를 요리조리 넘나들며 데이터숲을 헤쳐나가지만, 그 방식이 다르다.
개념이 정리되기 전엔 이게 뭐지 싶지만, 차근차근 정리해 보자.

1. DFS
주로 재귀의 성질을 이용해 구현한다.
재귀가 기본적으로 스택의 형태로 호출되기 때문에, DFS는 스택 자료구조를 이용한다 어쩌구 저쩌구 외울필요 없다.
게임 좀 해본 사람이라면 스택은 쌓인다는것을 모를리가 없기 때문에, 이해하는데에 큰 어려움은 없을것.
DFS가 동작하는 순서는 이렇다.

1. 탐색 시작 노드를 스택에 삽입한 후, 방문 처리를 한다.
2. 스택의 맨 위 노드와 연결된 노드(간선으로 직접 연결된, 인접노드) 중에, 방문해본적이 없는 노드들을 스택 맨 위에 넣는다.
   전부 방문해본 노드라면, 맨 위의 노드를 스택에서 꺼낸다.
3. 2번의 과정을 더이상 수행할 수 없을때까지 반복.

즉, 스택에 한 아이씩 계속 쌓고, 쌓다가 더 쌓을 아이가 없으면 스택에서 빼고, 또 쌓을 아이를 찾는 과정의 연속이다.
DFS의 포인트는, 방문 표시를 꼭 해야한다는 것이다.
방문표시를 하지 않으면 무한의 인피니티에 빠지기 때문에,,,
그래서 문제를 풀때 주어진 입력을 변형해 방문표시를 하거나 방문표시를 위해 데이터를 하나 마련하거나 한다.

2. BFS
이놈은 너비 우선 탐색이라는 이름답게, 일단 주위를 탐색한 후에 앞으로 나아간다.
주로 '큐(queue)' 구조와 함께 반복문과 환장의 콤비를 이룬다.
스택은 나중에 들어온 놈이 먼저 나가는 얄미운 녀석이었다면, 큐는 먼저 들어온 놈이 먼저 나가는 마음이 편안한 녀석이다.
그렇다고 머리가 편안하진 않지
BFS가 동작하는 원리는 이렇다.

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

즉, 방문한 녀석들의 인접 노드가 큐에 계속 쌓이고, 먼저 들어왔던 녀석들은 out되고.
쌓인 녀석들의 인접 노드가 큐에 또 쌓이고 그런 식이다. 

밍...말만 들으면 이게 뭐지 싶다.
글로 보기만 하면 어려운데, 그림으로보면 이상하게 참 쉽다. 동영상으로 보면 더 쉽다. 한번 같이 보자.

 

 

#4 활용

그럼 BFS는 언제쓰고 DFS는 언제써?
이건 문제를 많이 풀어봐야 감이 잡힌다는데,,,,난 아직 잘 모르겠다.
최단거리를 찾는 문제들은 BFS를 주로 사용, 이동간의 가중치가 있거나 제약이 있다면 DFS를 주로 사용,,,
뭐 더 풀어봐야 알겠지. 일단 문제부터 풀어보쟈.

 

 

#참고

https://devuna.tistory.com/32

[알고리즘] 깊이 우선 탐색(DFS) 과 너비 우선 탐색(BFS)

https://developer-mac.tistory.com/64

[코딩테스트 대비] DFS, BFS 정리

https://covenant.tistory.com/132

DFS BFS란? 백준 문제추천