**백준 1260번 DFS와 BFS(C++)

develop.me.z 2020. 12. 30. 00:17

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

1260번: DFS와 BFS

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

www.acmicpc.net

#include <iostream>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

void dfs(int start, vector<int> graph[], bool check[]){
    if(!check[start]){
        check[start]=true;
        cout<<start<<" ";
        for(int i=0;i<graph[start].size();i++){
            dfs(graph[start][i],graph,check);
        }
    }
}

void bfs(int start, vector<int> graph[], bool check[]){
   queue<int> q;//queue선언
   q.push(start);
   check[start]=true;//start도 넣어야함 
   
   while(!q.empty()){
       int tmp=q.front();
       q.pop();
       cout<<tmp<<" ";
       for(int i=0;i<graph[tmp].size();i++){
           if(check[graph[tmp][i]]==false){
               check[graph[tmp][i]]=true;
               q.push(graph[tmp][i]);
           }
       }
   }
}

int main()
{
    int n, m, v;
    cin>>n>>m>>v;
    
    vector<int> *graph = new vector<int>[n+1];
    bool *check = new bool[n+1];
    fill(check, check+n+1, false);
    
    for(int i=0;i<m;i++){
        int u,v;
        cin>>u>>v;
        
        graph[u].push_back(v);
        graph[v].push_back(u);
    }
    
    for(int i=0;i<=n;i++){
        sort(graph[i].begin(), graph[i].end());
    }
    
    dfs(v, graph, check);
    cout<<endl;
    
    fill(check,check+n+1,false);
    
    bfs(v, graph, check);
    cout<<endl;
    
    return 0;
}

https://codingffler.tistory.com/6

<참고>

1. [C++]백준 알고리즘 1260번: DFS와 BFS - 코딩도치

안녕하세요. 코딩도치 입니다~ 오늘은 백준 알고리즘 1260번 DFS와 BFS 문제를 풀어보려고 합니다! DFS, BFS는 코딩 테스트나 알고리즘 대회 같은 곳에 꼭 등장하는 단골손님입니다. 그러니까 꼼꼼히

codingffler.tistory.com

1. [C++]백준 알고리즘 1260번: DFS와 BFS - 코딩도치

codingffler.tistory.com