[BOJ][C++] 백준 1260번: DFS와 BFS

문제

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

 

문제 이해

• 그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과 출력

 

문제 풀이

주어진 간선과 두 정점의 번호를 이용해 인접 행렬을 저장한다.

 

💡 DFS

현재 정점과 연결된 정점을 순서대로 재귀 탐색한다.

시작 V → V와 연결된 정점 A → A와 연결된 정점 B → B와 연결된 정점 C ..

• 인접 행렬 adj[cur][1 ~ n] 순회. 연결되어 있으면 dfs(next)
• dfs 탐색하면서 방문 표시 & 출력 배열에 삽입하기
• 이미 방문한 곳이면 return

💡 BFS

현재 정점과 연결된 정점을 모두 큐에 삽입하고 큐에서 정점을 꺼내면서 탐색한다.

시작 V → V와 연결된 정점 A → V와 연결된 정점 B → …
A와 연결된 정점 A’ → A’와 연결된 정점 A’’ → …
B와 연결된 정점 B' → B’와 연결된 정점 B’’ → …

• 시작 정점부터 큐에 삽입하여 큐가 빌 때까지 순회한다.
• 큐에서 꺼낸 현재 정점을 탐색한다.
  • 인접 행렬 adj[cur][1 ~ n] 순회. 연결되어 있고 방문 안 한 정점이면 큐에 저장
  • 탐색하면서 방문 표시 & 출력 배열에 삽입하기

 

코드

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

using namespace std;

int n, m, v;
vector<vector<bool>> adj;
vector<bool> visited_dfs;
vector<int> ans_dfs;

void dfs(int cur)
{
    if (visited_dfs[cur])
        return;

    visited_dfs[cur] = true;
    ans_dfs.push_back(cur);
    for (int next = 1; next < n + 1; next++)
    {
        if (adj[cur][next])
            dfs(next);
    }
}

vector<int> bfs()
{
    queue<int> q;
    vector<int> visited_bfs(n + 1, false);
    vector<int> ans_bfs;

    q.push(v);
    visited_bfs[v] = true;

    while(!q.empty()){
        int cur = q.front();
        ans_bfs.push_back(cur);
        q.pop();
        
        for(int next = 1; next < n + 1; next++){
            if (!adj[cur][next] || visited_bfs[next])
                continue;
            visited_bfs[next] = true;
            q.push(next);
        }
    }

    return ans_bfs;
}

int main()
{
    // 입력
    int a, b;
    cin >> n >> m >> v;

    adj.assign(n + 1, vector<bool>(n + 1, false));
    visited_dfs.assign(n + 1, false);

    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        adj[a][b] = true;
        adj[b][a] = true;
    }

    // 연산
    dfs(v);

    // 출력
    for (int i : ans_dfs)
        cout << i << ' ';
    cout << '\n';
    for (int i: bfs())
        cout << i << ' ';

    return 0;
}