모든 경우의 수를 시도하는 방법
Exhaustive search, Brute force
- 상대적으로 구현이 간단하고, 해가 존재하면 항상 찾게 됨
- 경우의 수에 따라 실행 시간이 비례하기 때문에 입력 값의 범위가 작은 경우 유용.
// bfs, 큐 사용, 인접행렬, i 정점부터 시작
public static void bfs(int i) {
Queue<Integer> q = new LinkedList<>();
q.offer(i);
visit[i] = true;
while(!q.isEmpty()) {
int temp = q.poll();
for(int j=1; j<n+1; j++) {
if(map[temp][j] == 1 && visit[j] == false) {
q.offer(j);
visit[j] = true;
}
}
}
}
// dfs, 재귀, 인접 행렬, i 정점부터 시작
public static void dfs(int i) {
visit[i] = true;
for(int j=1; j<n+1; j++) {
if(map[i][j] == 1 && visit[j] == false) {
dfs(j);
}
}
}
// 모든 숫자 조합 만들기 (dfs)
public void dfs(String numbers, String tmp, int depth) {
if (tmp.length() == depth) {
int number = Integer.parseInt(tmp);
if(!arrNum.contains(number)) arrNum.add(number);
return;
}
else {
for(int i = 0; i < numbers.length(); i++) {
if(!visit[i]) {
visit[i] = true;
tmp += numbers.charAt(i);
dfs(numbers, tmp, depth);
isit[i] = false;
tmp = tmp.substring(0, tmp.length() - 1);
}
}
}
}
// 소수찾기
boolean isPrime(int number) {
if(number == 0 || number ==1) return false;
for(int i = 2; i <= Math.sqrt(number); i++){
if(number % i == 0) return false;
}
return true;
}