백준 1260 DFS와 BFS / C++

문제 : 링크텍스트

풀이 point

dfs, bfs를 구현한다.

풀이 순서

1. 그래프 자료구조를 활용하여 그래프 그리기(양방향 그래프임을 명심)
2. 방문 순서가 노드 값이 작은 순서부터이므로 각 노드마다 연결된 노드를 정렬
3. bfs, dfs 구현

코드

2025 01 10 버전으로 수정

//백준 1260, DFS와 BFS

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

int N, M, V;
std::vector<int> graph[1001];
std::queue<int> q;
bool visit1[1001];
bool visit2[1001];

void dfs(int k){
    if(visit1[k]) return;
    visit1[k] = true;
    std::cout << k << ' ';
    for(auto c : graph[k]){
        if(visit1[c]) continue;
        dfs(c);
    }
}

void bfs(){
    visit2[V] = true;
    q.push(V);
    while(!q.empty()){
        auto curr = q.front(); q.pop();
        std::cout << curr << ' ';
        for(auto c : graph[curr]){
            if(visit2[c]) continue;
            visit2[c] = true;
            q.push(c);
        }
    }
}

int main(){
    
    std::cin >> N >> M >> V;

    for(int i{0}; i<M; ++i){
        int a, b;
        std::cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

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

    dfs(V);
    std::cout << '\n';
    bfs();
    
    
    return 0;
}

2024-10-31T04:13:17.785Z