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

문제

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

 

---

 

백준 실버2 / dfs와 bfs

 

늘 개념은 알고 있었지만, 각잡고 제대로 문제 풀어본건 처음인듯

놀랍게도 1시간동안 삽질함..^^  (욕하지마세요 응애)

 

그래도 삽질한 만큼 뇌에 제대로 박혔다.

이제 다른 그래프 문제들은 쉽게 풀 수 있을거야 과연

 

기억해둬라 미래의 멍청한 나야

1. bfs는 무조건 queue 쓰는게 정석임 꼼수ㄴㄴ
2. dfs 재귀로 풀거면 전역변수 필수.
3. 그래프 문제는 입력받자마자 matrix로 저장해놓으면 나중에 편하다

 

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

int n;
int m;
int v;
int mat[1001][1001];

int dfs_visited[1002] = {0}; // dfs는 재귀로 풀거라서 전역변수 배열 visited 필요

int dfs(int V){
    cout << V << " ";
    dfs_visited[V] = 1;
    for (int i = 1; i <= n; ++i){
        if(dfs_visited[i]==1 || mat[V][i] == 0) continue; // 이미 방문했거나 mat에 없다면 스킵
        // V = i
        dfs(i);
    }
    return 0;
}

int bfs(int V){
    int bfs_visited[1002] = {0};
    queue<int> q; // bfs는 항상 queue를 사용한다.
    q.push(V);
    bfs_visited[V] = 1;
    while(!q.empty()){
        int x = q.front();
        cout << x << " ";
        q.pop();
        for (int i = 1; i <= n; ++i){
            if(bfs_visited[i]==1 || mat[x][i] == 0) continue; // 이미 방문했거나 mat에 없다면 스킵
            q.push(i);
            bfs_visited[i] = 1;
        }
    }
    return 0;
}

int main(){
    
    cin >> n >> m >> v;
    int x, y;
    for (int i = 0; i < m; ++i) {
        cin >> x >> y;
        mat[x][y] = mat[y][x] = 1; // 매트릭스로 그래프 표현
    }
    int V = v;
    dfs(V);
    cout << "\n";
    bfs(V);
    return 0;
}