깊이 우선 dfs 와 넓이 bfs 우선 검색 총 결 + 예제

DFS (Deep First Search) 깊이 우선 검색
깊이 우선 옮 겨 다 니 기 (dfs) 는 연 결 된 그림 을 옮 겨 다 니 는 알고리즘 입 니 다.그의 사상 은 하나의 정점 에서 시작 하여 한 길 을 따라 끝까지 가 는 것 이다. 만약 에 목표 해 에 도달 하지 못 하 는 것 을 발견 하면 이전 노드 로 돌아 간 다음 에 다른 길 을 끝까지 가 는 것 이다. 이런 최대한 깊 은 곳 으로 가 는 개념 은 바로 깊이 가 우선 하 는 개념 이다.
요컨대 남쪽 벽 에 부 딪 히 지 않 으 면 뒤 돌아 보지 않 는 다
템 플 릿 은 다음 과 같 습 니 다:

void dfs(int t)//t    dfs   
{
    if(      ||     )
    {
           ;
        return;
    }
    else
    {
        for(int i=1;i<=     ;i++)
            if(         )
            {
                                ;
                dfs(t+1);
                          ;//     {    }
            }
    }
}

예 1: 낙 곡 P1219 8 황후

#include
using namespace std;
int a[14],b[14],c[29],d[29];//    、 、    、        
int n;
int cnt=0;
void print()
{
    cnt++;
    if(cnt<=3)
    {
        for(int i=1;i<=n;i++)
            cout<>n;
dfs(1);
cout<

예제 2: 우 객 망 소우 의 행렬

#include
using namespace std;
long long a[52][52];
int n;
set s; //set          

void dfs(int x,int y,int sum){
    if(x==n && y==n){
        s.insert(sum);  //  （n,n）  sum    s
        return;
    }
    if(x+1<=n){
        dfs(x+1,y,sum+a[x+1][y]);//   
    }
    if(y+1<=n){
        dfs(x,y+1,sum+a[x][y+1]);//   
    }
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cin>>a[i][j];   //    
        }
    }
    dfs(1,1,a[1][1]);   //    
    cout<

BFS (Breath First Search) 범위 우선 검색
범위 우선 검색 의 깊이 우선 검색 의 차이 점 은 깊이 우선 검색 은 몇 개의 갈림길 이 있 든 지 간 에 먼저 길 을 끝까지 가 고 성공 하지 못 하면 이전 길목 으로 돌아 간 다음 갈림길 을 선택 하 는 것 이다. 그리고 범위 우선 검색 은 한 길목 에 직면 했 을 때 모든 갈림길 을 기록 한 다음 에 그 중의 하 나 를 선택 하여 들 어 가 는 것 을 목적 으로 한다.그리고 그것 의 분기 상황 을 기록 한 후에 다시 돌아 와 다른 갈림길 로 들 어가 이런 조작 을 반복 한다.
한 마디 로 카펫 검색 이나 물결 무늬 처럼 사방 으로 흩 어 져 있다.
템 플 릿 은 다음 과 같 습 니 다:

//     queue  ，             
void bfs()
{
         q
    q.push(  )；
         ；
    while(!q.empty())
    {
             u；
         q.pop();//      
         for(int i=0;i

예제 1: 낙 곡 P1443 말의 편력
이 문 제 는 말 이 어떤 점 에서 어떤 점 에 도달 하 는 데 최소 몇 걸음 걸 어야 하 며, 우선 bfs 를 사용 해 야 한다.

#include
using namespace std;
int h[8]={-2,-1,1,2,-2,-1,1,2},z[8]={1,2,2,1,-1,-2,-2,-1};//8    
int vis[410][410];
int cnt[410][410];//             
queue >q;
int n,m;
void bfs()
{
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int i=0;i<8;i++)
        {
            int xx=x+h[i];
            int yy=y+z[i];
            if(xx>n||xx<1||yy>m||yy<1||vis[xx][yy]==1)continue;//                
            q.push(make_pair(xx,yy));
            vis[xx][yy]=1;
            cnt[xx][yy]=cnt[x][y]+1;
        }
    }
}
int main()
{
    memset(cnt,-1,sizeof(cnt));
    int x,y;
    cin>>n>>m>>x>>y;
    vis[x][y]=1;
    cnt[x][y]=0;
    q.push(make_pair(x,y));
    bfs();
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=m;j++)
        {
            printf("%-5d",cnt[i][j]);//    
        }
        cout<

예제 2: 낙 곡 P1162 채 우기 색상
이 문제 의 관건 은 광 수 를 통 해 1 외곽 의 0 을 표시 하 는 것 이다.

#include
using namespace std;
int h[4]={-1,0,1,0},z[4]={0,-1,0,1};
int n,a[35][35]; 
queue >q;
int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            cin>>a[i][j];
    for(int i=0;i<=n+1;i++)//    0,      0    
    {
        a[0][i]=0;
        a[n+1][i]=0;
        a[i][0]=0;
        a[n+1][i]=0;
    }
    q.push(make_pair(0,0));
    while(!q.empty())
    {
        int x=q.front().first;
        int y=q.front().second;
        q.pop();
        for(int i=0;i<4;i++)
        {
            int x2=x+h[i];
            int y2=y+z[i];
            if(x2>=0&&y2>=0&&x2<=n+1&&y2<=n+1&&a[x2][y2]==0)
            {
                a[x2][y2]=-1;//1   0   -1
                q.push(make_pair(x2,y2));   
            }
        }
    }
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==-1)cout<

종합 하면 많은 문제 dfs 와 bfs 를 풀 수 있 지만 최 단 (우) 경로 문제 에 있어 서 는 넓 은 범위 로 bfs 를 우선 하 는 것 이 좋 습 니 다.
다음으로 전송:https://www.cnblogs.com/jiyi-conding/p/11402680.html