1R/워밍업문제

오늘의 문제

• BFS
• 넣기

참가자

• 15이원준, 박인서, 곽정흠

코드(DFS와 BFS)

박인서

#include <cstdio>
#include <vector>
#include <queue>
#include <algorithm>
 
std::vector<int> a[1001];
bool visit[1001] = { false, };
 
void dfs(int s, int n) {
    visit[s] = true;
    printf("%d ", s);
 
    for (int i = 0; i < a[s].size(); i++) {
        if (!visit[a[s][i]]) dfs(a[s][i], n);
    }
}
 
void bfs(int s, int n) {
    std::queue<int> q;
 
    for (int i = 1; i <= n; i++)
        visit[i] = false;
    q.push(s);
    visit[s] = true;
 
    for (int i = 0; !q.empty(); i++) {
        int qf = q.front();
        for (int j = 0; j < a[qf].size(); j++) {
            if (!visit[a[qf][j]]) {
                q.push(a[qf][j]);
                visit[a[qf][j]] = true;
            }
        }
        printf("%d ", q.front());
        q.pop();
    }
}
 
int main()
{
    int n, m, v;
    scanf("%d %d %d", &n, &m, &v);
    for (int i = 0; i < m; i++) {
        int x, y;
        scanf("%d %d", &x, &y);
        a[x].push_back(y);
        a[y].push_back(x);
    }
 
    for (int i = 1; i <= n; i++)
        std::sort(a[i].begin(),a[i].end());
 
    dfs(v, n);
    printf("\n");
    bfs(v, n);
 
    return 0;
}

코드(상자 넣기)

아이디어