[백준] 1260번 DFS/BFS

#include <bits/stdc++.h>
#define fastio cin.tie(0)->sync_with_stdio(0)
#define MAX 1001
typedef long long ll;
using namespace std;

// DFS와 BFS
int N,M,V; //정점, 간선, 시작 정점 번호
int near[MAX][MAX]; //인접 행렬 그래프
bool visited[MAX]; //정점 방문 여부
queue<int> q;

void reset(){
    for(int i=1; i<=N; i++){
        visited[i]=0;
    }
}

void DFS(int v){
    visited[v] = true;
    cout<<v<<" ";
    for(int i=1; i<=N; i++){
        if(near[v][i]==1 && visited[i]==0){
            DFS(i);
        }
    }
}
void BFS(int v){
    q.push(v);
    visited[v]=true;
    cout<< v << " ";
    while(!q.empty()){
        v=q.front();
        q.pop();
        
        for(int w=1; w<=N; w++){
            if(near[v][w]==1 &&visited[w]==0){
                q.push(w);
                visited[w]=true;
                cout<<w<<" ";
            }
        }
    }
}
int main(){
    cin>>N>>M>>V; //정점, 간선
    for(int i=0; i<M; i++){ //간선 입력
        int a,b;
        cin>>a>>b;
        near[a][b]=1;
        near[b][a]=1;
    }
    reset();
    DFS(V);
    cout<<'\n';
    reset();
    BFS(V);
    
    return 0;
}

 

<풀이>

DFS: 재귀 함수로 구현함, stack을 사용하면 비재귀로 구현할 수 있음

BFS: queue로 구현함

DFS는 깊이 우선 탐색, BFS는 넓이 우선탐색

 

> BFS 동작

1. 탐색 시작 노드를 큐에 삽입하고 방문 처리를 한다.
2. 큐에서 노드를 꺼내 해당 노드의 인접 노드 중에서 방문하지 않은 노드를 모두 큐에 삽입하고 방문 처리를 한다.
3. 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

<참고 사이트>

https://scarlettb.tistory.com/76