백준 1260: DFS와 BFS

깊이우선탐색과 넓이우선탐색의 개념을 잡는 문제, 숫자 순서대로 방문되므로 입력되는 값들을 정렬해주고 또한 간선이 양쪽에 있으니 이 또한 적용해주어야 시작점이 달라졌을 때 답을 올바르게 반영할 수 있다. 벡터를 재귀로 전달해서 그런지 메모리가 상당히 크게나왔다.

#include <iostream>
#include <queue>
#include <algorithm>
bool check_bfs[1005];
bool check_dfs[1005];
using namespace std;
 
void dfs(int start, vector<vector<int>> lst)
{
    //방문됬음을 표시
    check_dfs[start] = true;
    cout << start << " ";
    for (int i = 0; i < lst[start].size(); ++i)
    {
        int y = lst[start][i];
        //방문이 되지 않았다면 
        if (check_dfs[y] == false)
            dfs(y, lst);
    }
    return;
}
 
int main()
{
    int vertex, edge, start;
    cin >> vertex >> edge >> start;
    vector<vector<int>> list(vertex + 1);
    int input_1, input_2;
    for (int i = 0; i < edge; ++i)
    {
        cin >> input_1 >> input_2;
        list[input_1].push_back(input_2);
        list[input_2].push_back(input_1);
    }
    for (int i = 0; i < list.size(); ++i)
        sort(list[i].begin(), list[i].end());
    dfs(start, list);
    cout << endl;
    //bfs 시작
    queue<int> q;
    check_bfs[start] = true;
    q.push(start);
    while (!q.empty())
    {
        int x = q.front(); q.pop();
        
        cout << x << " ";
        for (int i = 0; i < list[x].size(); ++i)
        {
            if (check_bfs[list[x][i]] == false)
            {
                check_bfs[list[x][i]] = true;
                q.push(list[x][i]);
            }
        }
    }
    cout << endl;
    return 0;
}