반응형
백트래킹과 완전탐색에 대하여 헷갈려서 비교해보았다.
백트래킹의 대표적인 요소 DFS, BFS.
백준15649번: N과 M(1)
DFS로 풀이한 방식이다.
import java.io.IOException;
import java.util.Scanner;
class Main {
static int n, m;
static int[] arr = new int[9];
static boolean[] visited = new boolean[9];
public static void main(String[] args) throws IOException {
//input
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
m = scanner.nextInt();
comb(0);
}
static void comb(int k) {// 현재 k개까지 수를 택했음.
if (k == m) {//끝까지 탐색했다면 출력.
for (int i = 0; i < m; i++) {
System.out.print(arr[i] + " ");
}
System.out.println();
return;//한칸 위로 올라가기
}
for (int i = 1; i <= n; i++) {//1~N까지 수
if (!visited[i]) {//사용되지않은 값 i에 대하여
arr[k] = i;//arr[k]에 i값 저장
visited[i] = true;//해당 i사용완료
comb(k + 1);//사용한 i빼고 나머지에 대해서 재귀 ㄱㄱㄱ
visited[i] = false;//사용했던거 다시 내려놓기 다른i탐색하러 ㄱㄱ
}
}
}
}
comb메소드를 틀을 알아보자.
- 매개변수 : 시작노드를 0으로 주지만, 결론적으로 arr에 노드에 해당값이 들어갈것이다. visited도 방문여부를 기록하는데 사용. 따라서 전역변수 arr[], visited[] 와 현재 몇개까지 뽑았는지 알려주는 k값(m값과 비교용)이 있다. N과M은 어차피 정적인 변수기때문에 전역으로 하던 매개로 하던 노상관.
- 메소드를 끝내는 부분 : k==m(즉, m+1번 실행한것)일때 그동안 저장한 arr[]에 대하여 출력(단, 이때의 arr는 재귀의 한 뿌리에 불과하다.)
- for문 시작 : 재귀 앞에서 사용할값 arr에 저장 및 방문true한걸로 미리 설정.
- for문 중간 : 재귀(k+1)로 방문.
- for문 끝 : 재귀 뒤에선 사용했었던거 반납. 방문안함으로 false
다음은 마지막 for문의 작동방식을 보여주는 예시이다.
반응형
'코딩테스트 > 알고리즘 개념정리' 카테고리의 다른 글
그래프(Graph) 코드 구현 및 이해 (0) | 2021.04.07 |
---|---|
플로이드 워셜 알고리즘 (0) | 2020.12.01 |
그래프 이론(싸이클, 최소신장트리, 위상 정렬) (0) | 2020.11.25 |
DFS/BFS 개념정리 (0) | 2020.11.04 |
DP(=다이나믹 프로그래밍,Dynamic Programming) 심화 (0) | 2020.10.13 |