DFS

1. 방문하지 않은 이웃 정점들 중 선택하여 방문
2. 더 이상 방문할 정점이 없으면 퇴각.

방문 여부(초기값 -1)를 체크하는 정적 배열 전역 변수 필요

void backtrack(state){
	visit[state] = 1; // VISITED
	if ( End_state || Invalid_state) // 종료 혹은 가지치기
    	return; 
    for (neighbor case)
    	if(visit[neighbor] == -1){ // UNVISITED
    		backtrack(neighbor);
        }
}

 

재귀를 쓰는 이유 : 주사위 1번의 경우의 수 -> for문 1개가 필요  주사위 2번의 경우의 수 ->for문 2개 필요..  주사위 n번이면 ??

재귀의 단점 : 스택 오버플로우 ( 현업에선 거의 안씀 -> 알고리즘 문제를 풀기 위해서는 재귀적 마인드가 필요하므로 알아두자)

DFS

순열 트리 / 조합 트리

DFS(n+1, cost+A)로 호출. cost+=A 후 call 하는 경우에는 call이후에 cost-=A를 반드시 해야함.

각 단계에서 선택했던 것은 ans[]배열 같은 곳에 넣어두면 됨.

Tip)조합은 중복을 고려해야함.

중복이 없는 경우의 수(조합)는 현재 선택된 것 다음부터 넘겨준다.for(i=s -> 6)

 

Tip) DFS 가지치기

최소값 구할 때는 Sol < cnt 면 그전에 return;

최대값구할 때는 ? 총 소의 마리 – 남은소 + 현재 소의 마리  < sol 면 가볼 필요 없음.