[백준 알고리즘] 1260번 문제 DFS와 BFS

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

 

 

알고리즘 : DFS

언어: C++

 

이제 DFS와 BFS의 규칙을 알것같기도하고

그래프 개념 node, edge에 대해 많은 문제를 풀어봐야할것같음.

문제 요구사항을 만족하기 위해서 이런저런 함수를 가져다 써보았다.

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

int n;
int m;

vector<vector<int>> vec;
vector<int> visit;

vector<int> answer;
void dfs(int v) {
    visit[v] =1;
    answer.push_back(v);

    for(int i=1; i<=n; i++) {
        if (vec[v][i] == 1 && !visit[i]) {
            dfs(i);
        }
    }    
}

void bfs(int v) {
    queue<int> q;

    q.push(v);
    visit[v]=1;
    while (!q.empty()) {
        int target = q.front();
        answer.push_back(target);
        q.pop();
        for (int i = 1; i <=n; i++){
            if (vec[target][i] == 1 && !visit[i]) {
                q.push(i);
                visit[i] = 1;
            }
        }
    }
}
int main()
{
    int v;
    cin >> n >> m >> v;

    vec.resize(n+1,vector<int>(n+1,0));
    visit.resize(n+1);
    int from, to;

    // 데이터 셋팅(무방향그래프)
    for (int i = 0 ; i <m; i ++) {
        cin >> from >> to;
        vec[from][to] = 1;
        vec[to][from] = 1;
    }

    dfs(v);
    for(int i = 0; i < answer.size(); i++){
        cout << answer[i] << " ";
    }
    fill(visit.begin(), visit.end(), 0);
    answer.clear();
    
    bfs(v);
    cout << endl;
    for(int i = 0; i < answer.size(); i++){
        cout << answer[i] << " ";
    }
    return 0;
}