1260번: DFS와 BFS(13분)

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

구현 아이디어 0분 구현 13분

풀이

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int N{}, M{}, V{};
vector<int> Graph[1001];
int CheckDFS[1001], CheckBFS[1001];

void DFS(int V)
{
    CheckDFS[V] = 1;
    printf("%d ", V);

    for (size_t i = 0; i < Graph[V].size(); ++i)
    {
        if (CheckDFS[Graph[V][i]]) continue;
        CheckDFS[Graph[V][i]] = 1;
        DFS(Graph[V][i]);
    }
}

void BFS(int V)
{
    queue<int> Q;
    Q.push(V);
    CheckBFS[V] = 1;

    while (!Q.empty())
    {
        int CheckV = Q.front();
        Q.pop();

        printf("%d ", CheckV);

        for (size_t i = 0; i < Graph[CheckV].size(); ++i)
        {
            if (CheckBFS[Graph[CheckV][i]]) continue;
            CheckBFS[Graph[CheckV][i]] = 1;
            Q.push(Graph[CheckV][i]);
        }
    }
}

int main() {
    scanf("%d %d %d", &N, &M, &V);

    for (int i = 0; i < M; ++i)
    {
        int V1{}, V2{};
        scanf("%d %d", &V1, &V2);

        Graph[V1].push_back(V2);
        Graph[V2].push_back(V1);
    }

    for (int i = 1; i <= N; ++i)
    {
        sort(Graph[i].begin(), Graph[i].end());
    }
    
    DFS(V);
    printf("\n");
    BFS(V);
    
    return 0;
}