cpp) 백준 1260: DFS와 BFS
본문 바로가기
코딩 테스트/백준 (C++, Python)

cpp) 백준 1260: DFS와 BFS

by NEWSUN* 2023. 6. 9.

Problem

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

 

1260번: DFS와 BFS

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사

www.acmicpc.net

 
그래프를 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

오랜만에 풀어보는 DFS와 BFS 문제였다. 그래프 이론을 알고 있다면 어려운 문제는 아니다. DFS란? 깊이 우선 탐색(Depth First Search)라는 그래프 탐색 방법 중 하나로, 방문해 나갈 수 있는 정점이 있

kimyunseok.tistory.com

https://kimyunseok.tistory.com/25

 

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

vector 선언 시 []괄호와 ()괄호의 차이가 있다. []괄호로 선언시, 텅 빈 이차원 배열이라고 생각하면 된다. 각 벡터의 인덱스마다 동적으로 크기를 할당할 수 있다. ()괄호로 선언시, 처음에 그 공간

kimyunseok.tistory.com