백준 1260번 - DFS와 BFS

문제

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

예시 입력

5 5 3
5 4
5 2
1 2
3 4
3 1

예시 출력

3 1 2 5 4
3 1 4 2 5

아이디어

대놓고 DFS / BFS

알고리즘

DFS / BFS

소스코드

#include <bits/stdc++.h>
#define ALL 1010
using namespace std;

bool visitedDFS[ALL];
vector<int> DFSNode[ALL];
bool visitedBFS[ALL];
vector<int> BFSNode[ALL];

int N, M, V;

void dfs(int x) {
    visitedDFS[x] = true;
    cout << x << " ";
    for (int i = 0; i < DFSNode[x].size(); i++) {
        int y = DFSNode[x][i];
        if (!visitedDFS[y]) {
            dfs(y);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visitedBFS[start] = true;

    while (!q.empty()) {
        int x = q.front();
        cout << x << " ";
        q.pop();
        for (int i = 0; i < BFSNode[x].size(); i++) {
            int y = BFSNode[x][i];
            if (!visitedBFS[y]) {
                visitedBFS[y] = true;
                q.push(y);
            }
        }
    }

}

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

    int Val1, Val2;
    for (int i = 0; i < M; i++) {
        cin >> Val1 >> Val2;

        DFSNode[Val2].push_back(Val1);
        DFSNode[Val1].push_back(Val2);
        BFSNode[Val1].push_back(Val2);
        BFSNode[Val2].push_back(Val1);
    }

    for (int i = 1; i <= N; i++) {
        sort(DFSNode[i].begin(), DFSNode[i].end());
        sort(BFSNode[i].begin(), BFSNode[i].end());
    }/*주의!!!!!!!!!*/

    dfs(V);
    cout << "\n";
    bfs(V);
}

알아 가야할것

• DFS/BFS에서 간선을 저장할때 내림 차순으로 정렬해야한다.