BFS 완전탐색 알고리즘 [java]

완전탐색 알고리즘?

모든 경우의 수를 다 체크해서 정답을 찾는 방법이다. 

Brute Force라고도 한다. 

 

직관적이어서 이해하기 쉽고

문제의 정확한 결과값을 얻어낼 수 있는 가장 확실한

기초적인 방법이다. 

 

---

예시

4자리 암호로 구성된 자물쇠를 풀려고 한다. 
이 자물쇠가 고장난 것이 아니라면 가장 확실한 암호 찾는 방법은?
0000부터 9999까지 모두 시도해 보는 것이다. 
(최대 10,000번의 시도로 해결가능)

 

 

하지만

문제해결 알고리즘으로 BFS를 사용할 때는 2가지 규칙을 적용한다. 

1. 사용된 알고리즘이 적절한가? (알고리즘 통해 문제 해결할 수 있는지)

2. 효율적으로 동작하는가?

 

 

1번은 대부분 통과하지만, 2번 통과가 어렵다...

 

---

완전 탐색 기법 활용 방법

고려해야할 사항 3가지

1. 해결하고자 하는 문제의 가능한 경우의 수를 대략적으로 계산한다. 
2. 가능한 모든 방법을 다 고려한다. 
3. 실제 답을 구할 수 있는지 적용한다. 

 

2번의 모든방법? (중요)

- 단순 BF 기법 (반복/조건문 활용해 모두 테스트하기)

- 순열 n개의 원소 중 r개의 원소를 중복 허용 없이 나열하는 방법

- 재귀호출

- 비트마스크(2진수 표현 기법 활용)

- BFS, DFS 활용하는 방법

 

---

1. 단순 Brute Force

어느 기법 사용하지 않고,

단순하게 for문과 if문으로 모든 case 만들어 답을 구하는 방법이다. 

보통 아주 기초적인 문제에서 주로 이용되거나,

전체 풀이의 일부분으로 이용하며, 

대회나 코테에서는 이 방법만을 이용한 문제는 거의 나오지 않는다. 

 

2. 순열

완전탐색의 대표적인 유형이다. 

서로 다른 N개를 일렬로 나열하는 순열의 경우의 수는 N!

때문에 완전탐색을 이용하기 위해서는 N이 한자리 수 정도는 되어야 한다. 

 

3. 재귀 함수

재귀 함수를 통해서 문제를 만족하는 경우들을 만들어가는 방식

부분집합 문제를 예로 들면, 만들고자 하는 부분집합을 S라고 할 때, S ={ } 부터 시작해서 각 원소에 대해서 해당 원소가 포함이 되면 S에 넣고 재귀함수를 돌려주고, 포함이 되지 않으면 S를 그대로 재귀함수에 넣어주는 방식이다. 

비트마스크와 마찬가지로 주로 각 원소가 포함이 되거나, 포함이 되지 않는 두 가지 선택을 가질 때 이용된다.

 

4. 비트마스크

2진수를 이용하는 컴퓨터의 연산을 이용하는 방식이다.

완전 탐색에서 비트마스크는 문제에서 나올 수 있는 모든 경우의 수가

각각의 원소가 포함되거나, 포함되지 않는 두 가지 선택으로 구성되는 경우에 유용하게 사용 가능하다. 

간단한 예시로 원소가 5개인 집합의 모든 부분집합을 구하는 경우를 생각해보자. 

어떤 집합의 부분집합은 집합의 각 원소가 해당 부분집합에 포함되거나, 포함되지 않는 두 가지 경우만 존재한다.

따라서 5자리 이진수 (0~31)를 이용하여 각 원소의 포함 여부를 체크할 수 있다. 

 

5. BFS/DFS 활용

약간의 난이도 있는 문제로 완전탐색 + BFS/DFS 문제가 많이 나온다. 

대표적인 유형으로 길 찾기 문제가 있다. 

단순히 길을 찾는 문제라면 BFS/DFS만 이용해도 충분하지만, 주어진 도로에 장애물을 설치하거나, 

목적지를 추가하는 등의 추가적인 작업이 필요한 경우에 이를 완전탐색으로 해결하고 나서, BFS/DFS를 이용하는 방식이다.