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

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

1260번: DFS와 BFS

어떠한 그래프에 대한 깊이 우선 탐색과 너비 우선 탐색 결과를 각각 출력하면 되는 문제이다.

주의해야 할 점은 방문할 수 있는 정점이 여러 개인 경우 정점 번호가 작은 것을 먼저 방문한다는 것이다.

따라서 그래프를 sort함수를 통해 오름차순으로 정렬해줘야 한다.

입력받은 v부터 dfs를 실행한 결과를 출력하고 그래프를 다시 초기 상태로 돌려놔 bfs도 실행할 수 있도록 한다.

참고로 이때 i <=n인데 i <n으로 해놓은 걸 못 찾아서 맞왜틀을 계속 외쳤다.....

컴퓨터는 거짓말을 하지 않는다.. 거짓말은 내 뇌가 할 뿐.....

사소한 실수를 조심하자...

 

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

bool visited[1001];
vector<int>graph[10001];

void dfs(int x){
    cout << x << " ";
    visited[x] = true;
    for(int i:graph[x]){
        if(!visited[i]){
            dfs(i);
        }
    }
}

void bfs(int x){
    queue<int> q;
    q.push(x);
    while (!q.empty()) {
        int top = q.front();
        q.pop();
        if (visited[top]) {
            continue;
        }
        visited[top] = true;
        cout << top << " ";
        for (int i: graph[top]) {
            if (!visited[i]) {
                q.push(i);
            }
        }
    }
}

int main(){
    int n,m,v;
    cin >> n >> m >> v;
    for(int i=0;i<m;i++){
        int a,b;
        cin >> a>>b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    for(int i=1;i<=n;i++){
        sort(graph[i].begin(),graph[i].end());
    }

    dfs(v);
    cout << endl;
    for (int i = 0; i <= n; i++) {
        visited[i] = false;
    }

    bfs(v);
}

 

 

https://github.com/farmJun/Algorithm_BOJ_PS/blob/main/%EA%B9%8A%EC%9D%B4%20%EC%9A%B0%EC%84%A0%20%ED%83%90%EC%83%89/1260.cpp

GitHub - farmJun/Algorithm_BOJ_PS: 백준 알고리즘 문제풀이 기록 레포짓입니다.