완전 탐색(Brute Force): DFS와 BFS

 

완전 탐색(Brute Force)은 주어진 데이터에서 가능한 모든 경우의 수를 시도하여 정답을 찾는 알고리즘이다.

시간복잡도 면에서는 불리하지만 문제의 입력 크기가 작을 때 유리하다.

 

DFS(Depth First Search)

• 하나의 탐색을 전부 온전히 수행할 때까지 진행
• 재귀 호출, 스택(LIFO)으로 구현
• 모든 경우의 수를 탐색해야 한다면 DFS
• 출발지에서 목적지에 도달할 수 있는지를 중점으로 탐색하는 완전 탐색 기법

재귀 방식과 똑같고, 구현이 편하다.

특히 문제에서 탐색 시 제약 조건을 붙이거나 결과가 누적되어야 하는 조건이 있다면,

하나의 경우의 수를 고유하게 취급해주기 위해 사용한다.

 

 

구현 로직

1. 시작 부분을 스택에 삽입하고 함수 호출
2. 해당 위치를 방문했다고 표시하고 작업 처리
3. 이동 가능한 방향을 하나씩 확인
4. 다음 위치가 유효하고 방문하지 않았으면 2번으로 돌아감
5. 유효하지 않으면 처리를 종료하고 스택에서 나옴

 

BFS(Breadth First Search)

• 현재 위치에서 탐색 가능한 모든 길을 확인하고 진행
• 큐(FIFO)로 구현(collection.deque)
• 최단 거리, 최소 비용 등 가장 적은 횟수로 답을 찾아야하면 BFS
• 가까운 노드부터 순차 탐색

while문을 사용하여 다음 탐색해야 할 위치를 큐에 저장하고 남은 큐가 없을 때까지 탐색한다.

 

 

구현 로직

1. 시작 위치를 큐에 추가하고 방문 처리
2. while문으로 큐가 빌 때까지 반복하면서
3. 큐에서 popleft()해서 현재 위치 처리
4. 현재 위치에서 이동 가능한 방향 확인하여
5. 유효하고 방문하지 않은 위치를 방문 처리하고 큐에 삽입하는 것을 반복