[백준1260번] BFS와 DFS

자료구조 시험공부 하다가 너무 재미없어서 ㅠㅠㅠ

문제푸는거 재밌는데, 수업이 너무.. (할많하않;)

 

방문할 수 있는 정점이 여러개인경우 작은것을 먼저 방문하라고 해서 

sort하고 시작했고,

입력으로 주어지는 간선은 양방향이라서 push_back 엇갈리게 푸쉬.

 

#include <bits/stdc++.h>

using namespace std;

int N, M, V;
vector<int> vec[1001]; // 총 노드수
bool visited[1001]; // 방문한 노드
queue<int> q; // bfs에서 사용할 거.

void dfs(int node, int d){
    if(d == N+1) return;
    for(int i = 0; i<(int)vec[node].size(); i++)
    {
        if(visited[vec[node][i]] ==0){
            visited[vec[node][i]] = 1;
            cout << vec[node][i] << " ";
            dfs(vec[node][i],d+1);
        }
    }
}
void bfs(int node){
    visited[node] =1;
    cout << node << " ";
    for(int i = 0 ; i<vec[node].size(); i++)
    {
        int v_node=vec[node][i];
        if(visited[v_node] == 0)
        {
            visited[v_node] = 1;
            q.push(v_node);
        }
    }

    while(!q.empty())
    {
        int here = q.front();
        cout << here<< " ";
        q.pop();
        for(int i = 0 ; i<vec[here].size(); i++)
        {
            int v_node = vec[here][i];
            if(visited[v_node] ==0)
            {
                visited[v_node] = 1;
                q.push(v_node);
            }
        }
    }

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

    for(int i = 0 ; i< M; i++)
    {
        int a, b;
        cin >> a >> b;
        vec[a].push_back(b);
        vec[b].push_back(a);
    }
    
    for(int i = 1 ; i<=N;i++)
    {
        sort(vec[i].begin(), vec[i].end());
    }

    
    
    visited[V] =1;
    cout << V << " ";

    dfs(V,1);
    cout << endl;

    memset(visited, 0, sizeof(visited));
    bfs(V);

}