[백준] 1260번 DFS와 BFS

문제

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

풀이과정

DFS와 BFS 구현에 대한 기본적인 문제이다. DFS는 벡터를 이용해 구현했고, BFS는 큐를 이용해 구현하였다. 문제에서 방문할 수 있는 정점이 여러개일 경우에는 정점 번호가 작은 것을 먼저 방문한다는 조건을 주었기 때문에 DFS와 BFS를 실행하기 전에 인접 리스트를 정렬 시켜줬다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

int N, M, V;
vector<int> a[1001];
bool chk[1001];

void DFS(int node)
{
    chk[node] = true;
    cout << node <<" ";
    for (int i = 0; i < a[node].size(); i++)
    {
        int next = a[node][i];
        if (chk[next] == false)
            DFS(next);
    }
}

void BFS(int start)
{
    queue<int> q;
    memset(chk, false, sizeof(chk));
    chk[start] = true; q.push(start);

    while (!q.empty())
    {
        int node = q.front(); q.pop();
        cout << node << " ";
        for (int i = 0; i < a[node].size(); i++)
        {
            int next = a[node][i];
            if (chk[next] == false)
            {
                chk[next] = true;
                q.push(next);
            }
        }
    }
}

int main()
{
    cin.sync_with_stdio(false);

    cin >> N >> M >> V;

    for (int i = 0; i < M; i++)
    {
        int x, y;

        cin >> x >> y;

        a[x].push_back(y); a[y].push_back(x);
    }

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

    DFS(V);
    cout << "\n";
    BFS(V);

    return 0;
}