백준 1260번: DFS와 BFS C++코드(DFS, BFS)

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

using namespace std;

vector <int> maps[1001];

void dfs(int v){
    stack <int> s;
    int visited[1001] = {0,};
    s.push(v);
    while(!s.empty()){
        int now = s.top();
        if(visited[now] == 0){
            cout << now << " ";
        }
        visited[now] = 1;
        s.pop();
        for(int i=maps[now].size()-1; i>=0; i--){
            if(visited[maps[now].at(i)] == 0){
                s.push(maps[now].at(i));
            }
        }
    }
}

void bfs(int v){
    queue <int> q;
    int visited[1001] = {0,};
    q.push(v);
    while(!q.empty()){
        int now = q.front();
        if(visited[now] == 0){
            cout << now << " ";
        }
        visited[now] = 1;
        q.pop();
        for(int i=0; i<maps[now].size(); i++){
            if(visited[maps[now].at(i)] == 0){
                q.push(maps[now].at(i));
            }
        }
    }

}

int main(){
    int n,m,v;
    int node1, node2;
    cin >> n >> m >> v;
    for(int i=0; i<m; i++){
        cin >> node1 >> node2;
        maps[node1].push_back(node2);
        maps[node2].push_back(node1);
    }
    for(int i=1; i<n+1; i++){
        sort(maps[i].begin(), maps[i].end());
    }

    dfs(v);
    cout << endl;
    bfs(v);
}

 

설명

단순한 dfs와 bfs를 구현하는 문제이다. 필자의 경우 dfs는 스택으로 bfs는 큐로 구현을 하였다.

 

문제점

각 탐색 방법을 잘 구현한 것 같은데 왜 틀리나해서 봤더니 인접리스트 정렬을 안해주어서 다시 정렬을 해주었다.