[ 백준 1260 ] DFS와 BFS (C++)

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

1260번: DFS와 BFS

 

DFS와 BFS의 원리만 알면 쉬운 문제다. 주의할 점은 노드간 간선 연결을 할 때 양방향이기 때문에 둘 다 연결해줘야 한다. 또한 작은 숫자부터 방문해야 하기 때문에 노드를 오름차순으로 정렬해줘야 한다. 벡터 또는 배열을 사용할 수 있는데 나는 벡터를 사용해서 풀었다. 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

int N, M, start, from, to;
int visit[1001];

void dfs(vector<vector<int>>& nodes, int start){
    cout << start << ' ';
    
    visit[start] = 1;
    
    for(int i = 0; i < nodes[start].size(); i++){
        if(!visit[nodes[start][i]])
            dfs(nodes, nodes[start][i]);
    }
    
}

void bfs(vector<vector<int>>& nodes, int start){
    queue<int> q;
    
    visit[start] = 1;
    q.push(start);
    
    while(!q.empty()){
        start = q.front();
        q.pop();
        cout << start << ' ';
        
        for(int i = 0; i < nodes[start].size(); i++){
            if(!visit[nodes[start][i]]){
                visit[nodes[start][i]] = 1;
                q.push(nodes[start][i]);
            }
        }
    }
}

int main(){
    
    cin >> N >> M >> start;
    
    vector<vector<int>> nodes(N + 1);
    
    for(int i = 0; i < M; i++){
        cin >> from >> to;
        // 양방향이기 때문에 둘 다 연결. 조심!
        nodes[from].push_back(to);
        nodes[to].push_back(from);
    }
    
    // 작은 숫자부터 방문
    for(vector<int>& v : nodes)
        sort(v.begin(), v.end());
    
    dfs(nodes, start);
    
    // 방문 행렬 초기화
    for(int i = 1; i <= N; i++)
        visit[i] = 0;
    
    cout << endl;
    
    bfs(nodes, start);
    
    return 0;
}