(매일 BOJ) C++ 1260번 DFS와 BFS

이번 문제는 1260번 DFS와 BFS 문제이다

접근법

 1. 그래프 표현

• 인접 리스트 방식 사용 (vector<int> v[1001])
• 정점 번호가 1부터 시작하므로 1001 크기로 선언
• 양방향 간선이므로 v[a].push_back(b)와 v[b].push_back(a) 모두 수행

2. 방문 순서 정렬

문제 조건에 따라 정점 번호가 작은 것부터 방문해야 하므로, 각 정점의 연결 리스트를 오름차순 정렬합니다

 3. DFS 구현

• 재귀 방식 사용
• 방문 체크는 visit_dfs 배열로 관리
• 방문한 정점은 result_dfs 벡터에 저장

4. BFS 구현

• 큐(queue) 사용
• 방문 체크는 visit_bfs 배열로 관리
• 방문한 정점은 result_bfs 벡터에 저장

핵심 포인트

• 그래프 탐색 문제에서는 방문 순서 조건을 항상 유의해야 합니다. 이 문제에서는 정점 번호가 작은 것을 먼저 방문해야 하므로 sort()가 필수입니다.
• visit 배열은 DFS, BFS 각각 따로 사용해야 합니다. 하나를 공유하면 두 알고리즘 중 하나가 이미 방문한 것으로 처리되어 탐색이 꼬일 수 있습니다. 혹은 visit을 초기화하고 다시 사용해야 함

작성코드

#include <bits/stdc++.h>
using namespace std;

vector<bool> visit_dfs(1001,false);
vector<bool> visit_bfs(1001,false);
vector<int> v[1001]; // 이차원 리스트로 저장 ex) v[1] = {2,3}
vector<int> result_dfs;
vector<int> result_bfs;
int N,M,V;

void DFS (int temp);
void BFS (int temp);

int main(void){
    ios::sync_with_stdio(false); cin.tie(0);
    
    cin >> N >> M >> V;

    for(int i = 0; i < M; i++){
        int a,b;
        cin >> a >> b;
        v[a].push_back(b);
        v[b].push_back(a); // 양방향 간선
        
    }

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

    DFS(V);
    BFS(V);

    for(int j : result_dfs) cout << j << ' ';
    cout << '\n';
    for(int o : result_bfs) cout << o <<' ';

    return 0;
}

void DFS (int V){
    visit_dfs[V] = 1;
    result_dfs.push_back(V);

    for(int i : v[V]){
        if(!visit_dfs[i]) DFS(i);
    }
}

void BFS (int V){
    queue<int> q;
    q.push(V);
    visit_bfs[V] = true;

    while(!q.empty()){
        int next = q.front();
        result_bfs.push_back(next);
        q.pop();

        for(int i : v[next]){
            if(!visit_bfs[i]){
                q.push(i);
                visit_bfs[i] = true;
            }
        }
    }
}