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

문제

 

 

시행 착오

 

 

해결 방법

 

벡터를 이용해 그래프를 구현하고, DFS 는 재귀호출을 통해, BFS 는 큐를 이용해 구현했다.

정점 순서대로 순회 하려면 입력 받은 뒤 sort를 해주어야 한다.

 

 

 

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

using namespace std;

int N, M, V;
vector<int> g[1001];
bool visited[10001] = { false };

queue<int> q;
vector<int> v_bfs;
vector<int> v_dfs;

void dfs(int node) 
{
    visited[node] = true;
    v_dfs.push_back(node);

    for (int nextnode : g[node]) 
    {
        if (!visited[nextnode]) 
        {
            dfs(nextnode);
        }
    }

}

void bfs(int node) 
{
    q.push(node);
    visited[node] = true;

    while (!q.empty())
    {
        int nextnode = q.front();
        q.pop();
        v_bfs.push_back(nextnode);
        
        for (int next : g[nextnode])
        {
            if (!visited[next])
            {
                visited[next] = true;
                q.push(next);
            }
        }


    }
}

int main() {
    cin >> N >> M >> V;

    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    for (int i = 1; i <= N; i++)
        sort(g[i].begin(), g[i].end());

    dfs(V);

    for (int i : v_dfs)
        cout << i << " ";
    cout << '\n';

    fill(visited, visited + 10001, false);

    bfs(V);

    for (int i : v_bfs)
        cout << i << " ";

    return 0;
}