0. DFS VS BFS

• 답이 되는 경로가 여러 개인 경우에도 최단 경로임을 보장한다. | | 언제 유리? | 찾아야 하는 노드가 깊은 단계에 있을수록, 그 노드가 좌측에 있을수록 유리 | 노드의 수가 적고 깊이가 얕은 해가 존재할 때 유리 | | 장점 | * 현 경로상의 노드를 기억하기 때문에 적은 메모리를 사용한다.
• 찾으려는 노드가 깊은 단계에 있는 경우 BFS보다 빠르게 찾을 수 있다. | * 답이 되는 경로가 여러 개인 경우에도 최단경로임을 보장한다.
• 최단 경로가 존재하면 깊이가 무한정 깊어진다고 해도 답을 찾을 수 있다. | | 단점 | * 해가 없는 경로를 탐색할 경우 단계가 끝날 때까지 탐색한다.
• DFS를 통해 얻어진 해가 최단 경로라는 보장이 없다. 해에 도착하면 탐색을 종료하기 때문이다. | * 경로가 매우 길 경우에는 탐색 가지가 급격히 증가함에 따라 많은 메모리를 필요로 한다.
• 해가 존재하지 않는다면 유한 그래프의 경우 모든 그래프를 탐색 후에 실패로 끝난다.
• 무한그래프의 경우 결코 해를 찾지도 못하고, 끝내지도 못한다. |

1. DFS

• 완전 탐색을 기본으로 하는 그래프 순회 기법으로, 모든 노드를 방문하는 것을 목표로 한다.

2. 백트래킹

• 불필요한 탐색을 하지 않고, 이전 단계로 돌아와 다른 후보해를 탐색해 나간다.
• 가지치기를 사용해서 유망하지 않은 부분을 쳐낸다.
  • ex) visit 배열 사용, 사용 가능한 갯수가 한정되어 있을 때
• 체크인, 체크아웃은 항상 같은 레벨에서 수행되어야 한다.
  • 첫 번째 코드는 맨 바깥에서 수행하는 경우, 두번째 코드는 맨 안쪽에서 수행하는 경우인데 둘은 수행의 순서에만 차이가 있고 다른 차이는 없다.
  • 두번째 코드는 가장 안쪽에서 체크인,체크아웃이 수행되므로 최초(시작점)의 갱신은 처음 dfs를 호출할 때 함께 수행해주어야 한다.

int[] visit = new int[N+1];

**dfs(1); //시작지점**

void dfs(int index){
	//1. 체크인
	**visit[index] = true;**
	//2. 목적지인가?
	if(~~~)
			return;
	//3. 연결된 곳을 순회
	for(int i=1;i<N;i++){
		//4. 갈 수 있는가? (가지치기)
		if(~~~~){
			//5. 간다
			dfs(i);
		}
	}
	//6. 체크아웃
	**visit[index] = false;**
}

int[] visit = new int[N+1];

**dfs(1); //시작지점
visit[1] = true; //미리 지정** 

void dfs(int index){
	//2. 목적지인가?
	if(~~~)
			return;
	//3. 연결된 곳을 순회
	for(int i=1;i<N;i++){
		//4. 갈 수 있는가? (가지치기)
		if(~~~~){
			//5. 간다
			**visit[index] = true;** //1. 체크인
			dfs(i);
			**visit[index] = false;** //6. 체크아웃
		}
	}
}

• M개의 동전이 3개씩 존재한다. 동전들을 이용하여 K를 만들 수 있는지 판별하시오
  • 모든 동전을 사용해서 만들 수 있는 조합을 구할 수 있다.

int[] coin = new int[M+1];
Arrays.fill(coin,3); //3개로 초기화

boolean dfs(int now, int index){
	//2. 목적지인가?
	if(index>=M){
		if(K를 만들었니?) return true;
		else return false;
	}
	//3. 연결된 곳 탐색
		for(int i=1;i<M+1;i++){ //가지고 있는 모든 동전의 종류들을 탐색한다.
			//4. 갈 수 있는가?
			if(coin[i] > 0){ //1개이상이면 갈 수 있음
				//1. 체크인
				coin[i]--;
				//5. 간다
				dfs(now + whatCoin[i], index+1);
				//6. 체크아웃
				coin[i]++;
		}
	}
}

백트래킹을 이용한 조합 구하기

static boolean[] visit = new boolean[N];
static ArrayList<Integer> Active = new ArrayList<>();

//N개 고르기
combination(0,0);

static void combination(int index,int count) {
		if(count>=N) {
			System.out.println(Active); //N개 조합 완성
			return;
		}
		for(int i=**index**;i<N;i++) {
			if(!visit[i]) {
				visit[i] = true;
				Active.add(i);
				**dfs(i+1,count+1);**
				visit[i] = false;
				Active.remove(Active.size()-1);
			}
		}
	}

백트래킹을 이용한 순열 구하기

static int[] Order = new int[10+1]; //말 순서 1~10

permutation(1);
combination(1,1);

static void permutation(int count){
  if(count>=4){
      System.out.println(Arrays.toString(Order));
      return;
  }
  for(int i=1;i<5;i++){ //말 1~4
      Order[count] = i; //말i가 Order 순서에 들어감
      permutation(count+1);
  }
}

static void combination(int index, int count){
  if(count>=4){
      System.out.println(OrderArr);
      return;
  }
  for(int i=index;i<5;i++){
      OrderArr.add(i);
      combination(i+1,count+1);
      OrderArr.remove(OrderArr.size()-1);
  }
}

[1, 2, 3]
[1, 2, 4]
[1, 3, 4]
[2, 3, 4]

• 순열

3. 자식 트리 갯수