도 론 - DFS

              ，             。              ，          ，                 。              ，               ，          ，  coding     ，      。                 。

DFS: 깊이 우선 검색 은 가능 한 한 깊 은 곳 으로 진행 합 니 다. 나무의 앞 뒤 를 옮 겨 다 니 는 것 은 특정한 의미 에서 깊이 우선 검색 BFS 라 고 할 수 있 습 니 다. 넓 은 범위 에서 검색 하고 넓 은 범위 에서 출발 합 니 다. (물 과 유사) 수의 층 차 는 사실은 BFS 와 유사 합 니 다.
여 기 는 나무 로 유추 한다.
데이터 구조 상: DFS 는 스 택 stack 을 사용 하고 BFS 는 대기 열 을 사용 합 니 다. 공간 복잡 도 에서 볼 때 DFS 의 시간 복잡 도 O (n), BFS 의 시간 복잡 도 는 O (2n 2 ^ n 2n) 입 니 다.
대비: BFS 는 가장 짧 은 길 이라는 개념 이 존재 합 니 다. 층 별로 찾 는 것 이기 때 문 입 니 다.DFS 는 깊이 에서 출발 하기 때문에 최 단 로 의 성질 을 가지 고 있 지 않다.
DFS 와 BFS 는 역 추적 과 가지치기 에 관련 될 수 있 습 니 다.
예제 도입:

#include 
#include 
using namespace std;
//DFS      ,+  ,            
const int N=10;
//     
int path[N];//       
int n;
bool st[N];//         ,     true 。
//  st[N]  false 
void dfs(int u){
	if(u==n)//             
	{
		for(int i=0;i<n;i++){
			cout<<path[i]<<" ";
		}
		puts("");//   
		return;
	}
	//          ，        
	for(int i=0;i<n;i++){
		//!st[i] ：         
		if(!st[i]){
			path[u]=i;
			st[i]=true;//      i     
			dfs(u+1);//       
			st[i]=false;//     、      
		}
	}
} 

#include 
using namespace std;
int main(){
	
	cin>>n;
	dfs(0);//  0   ，       
	return 0;
}

DFS 의 또 다른 응용 프로그램: N 황후 의 문 제 를 복습 하 는 김 에 재 귀 합 니 다.도입 예제: Acwing - 843. n - 황후 문제 leetcode - 51. N 황 후 는 사실 이 두 문제 가 똑 같 습 니 다. 여 기 는 세 가지 방법 을 통 해 앞의 두 가지 방법 으로 심도 있 는 우선 검색 을 사용 합 니 다. 바로 약간 격식 적 으로 바 뀌 었 습 니 다.

#include 
using namespace std;
const int N=20;
int n;
bool col[N],N_dg[N],P_dg[N];
char oc[N][N];

//     
void dfs(int u){
    if(u==n){
        for(int i=0;i<n;i++){
            puts(oc[i]);
        }
        puts("");
        return;
    }
    for(int i=0;i<n;i++){
        //  +  
        if(!col[i]&&!N_dg[u+i]&&!P_dg[n-u+i]){
            oc[u][i]='Q';
            col[i]=N_dg[u+i]=P_dg[n-u+i]=true;
            dfs(u+1);
            col[i]=N_dg[u+i]=P_dg[n-u+i]=false;
            oc[u][i]='.';
        }
    }
}
int main(){
    cin>>n;   
    for(int i=0;i<n;i++){
        for(int j=0;j<n;j++){
            oc[i][j]='.';
        }           
    }
    //  dfs  
    dfs(0);
    return 0;
}

leetcode 의 문제 풀이:
어떻게 행렬 에서 깊 은 수색 을 진행 합 니까?일반적인 사고방식 은 마치 우리 가 다음 기 에 하 는 것 과 같다.

#include 
using namespace std;
const int N=20;

bool col[N],row[N],N_dg[N],P_dg[N]; 
char oc[N][N];
int n;//n       ，            
//s          
void dfs(int x,int y,int s){
	//         
	if(y==n) y=0,x++;
	if(x==n){
		if(s==n){
			for(int i=0;i<n;i++){
				puts(oc[i]);
			}
			puts("");
		}
		return;
	} 
	
	//      ，         
	
	//    ,        ，       
	dfs(x,y+1,s);
	//    .  ：   ，   ，           
	if(!row[x]&&!col[y]&&!N_dg[x+y]&&!P_dg[x-y+n]){
		oc[x][y]='Q';
		//    ，    ，   
		row[x]=col[y]=N_dg[x+y]=P_dg[x-y+n]=true;
		//      
		dfs(x,y+1,s+1);
		row[x]=col[y]=N_dg[x+y]=P_dg[x-y+n]=false;
		oc[x][y]='.'; 
	} 
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		for(int j=0;j<n;j++){
			oc[i][j]='.';//                  . 
		}
	}
	//           ，          
	//          ，           
	dfs(0,0,0);
	return 0;
}