백준 1260 : DFS와 BFS

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

1260번: DFS와 BFS

 

#include <iostream>
#include <stack>
#include <queue>
 
bool mat[1010][1010];
bool visited[1010];
int n, m, v;
 
void input()
{
    std::cin >> n >> m >> v;
    for (int y = 0; y < m; ++y)
    {
        int from, to;
        std::cin >> from >> to;
        mat[from][to] = true;
        mat[to][from] = true;
    }
}
 
void dfs()
{
    std::stack<int> dfs;
    dfs.push(v);
    while (dfs.empty() == false)
    {
        int currPos = dfs.top();
        dfs.pop();
        if (visited[currPos] == true)
        {
            continue;
        }
        visited[currPos] = true;
        
        std::cout << currPos << ' ';
        for (int x = 1000; x > 0; --x)
        {
            if (mat[currPos][x] == true && visited[x] == false)
            {
                dfs.push(x);
            }
        }
    }
    std::cout << '\n';
}
 
void bfs()
{
    std::queue<int> bfs;
    bfs.push(v);
    while (bfs.empty() == false)
    {
        int currPos = bfs.front();
        bfs.pop();
        if (visited[currPos] == true)
        {
            continue;
        }
        visited[currPos] = true;
 
        std::cout << currPos << ' ';
        for (int x = 1; x <= 1000; ++x)
        {
            if (mat[currPos][x] == true && visited[x] == false)
            {
                bfs.push(x);
            }
        }
    }
}
 
void solve()
{
    dfs();
    for (int i = 0; i < 1010; ++i)
    {
        visited[i] = false;
    }
    bfs();
}
 
void output()
{
 
}
 
int main()
{
    input();
    solve();
    output();
    return 0;
}

 

벡터로 가지 않으면 시간초과가 날까 조마조마했지만

 

별 상관은 없었다

 

그러니 다시한번 기억하자 dfs는 스택, bfs는 큐