cpp) 백준 1260: DFS와 BFS

Problem

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 
그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하시오. 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문하고 더 이상 방문할 수 없는 경우 종료한다. 정점 번호는 1번부터 N번까지!
 

 
 

Solution

#include<iostream>
#include<queue>

using namespace std;
#define MAX 1001

int n, m, v;  // 정점의 개수, 간선의 개수, 탐색 시작할 정점 개수
int map[MAX][MAX];  // 인접 행렬 그래프
bool visited[MAX];  // 정점 방문 여부
queue<int> q;

// 정점 방문 여부 초기화 함수
void reset(){
    for(int i=1;i<=n;i++){
        visited[i]=0;
    }
}

// DFS 수행
void DFS(int v){
    visited[v]=1;
    cout << v << ' ';

    for(int i=1;i<=n;i++){
        if (map[v][i]==1 && visited[i]==0){
            // 현재 정점과 연결되어 있고 방문한 적이 없는 경우
            DFS(i);
        }
    }
}

// BFS 수행
void BFS(int v){
    q.push(v);
    visited[v]=1;
    cout << v << ' ';

    while(!q.empty()){
        v=q.front();
        q.pop();

        for(int i=1;i<=n;i++){
            if (map[v][i]==1 && visited[i]==0){
                // 현재 정점과 연결되어 있고 방문한 적이 없는 경우
                q.push(i);
                visited[i]=1;
                cout << i << ' ';
            }
        }
    }

}


int main(){
    ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
    
    cin >> n >> m >> v;

    for(int i=0;i<m;i++){
        int a, b;
        cin >> a >> b;
        // 정점 a와 b를 간선으로 연결
        map[a][b]=1;
        map[b][a]=1;
    }

    reset();
    DFS(v);

    cout << '\n';

    reset();
    BFS(v);
    
   return 0;
}

 
 

Reference

https://kimyunseok.tistory.com/26

[C++] 백준 1260번 DFS와 BFS

https://kimyunseok.tistory.com/25

[C++] 벡터 사용 시, () 선언과 [] 선언의 차이