22 삐약 : 백준 1260 [C++]

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

1260번: DFS와 BFS

 

#include<iostream>
#include<queue>


using namespace std;

int line[1001][1001];
bool visited[1001];
int n, m, v;
queue<int> q;
void dfs(int idx) {
    cout << idx << ' ';

    for (int i = 1; i <= n; i++) {
        if (line[idx][i] && !visited[i])
        {
            visited[i] = true;
            dfs(i);
        }
    }


}
void bfs(int idx) {

    q.push(idx);

    while (!q.empty()) {

        idx = q.front();

        q.pop();

        cout << idx << ' ';

        for (int i = 1; i <= n; i++) {
            if (line[idx][i] && !visited[i]) {
                q.push(i);
                visited[i] = true;
            }
        }


    }


}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    cin >> n >> m >> v;


    for (int i = 0; i < m; i++) {
        int from, to;
        cin >> from >> to;
        line[from][to] = 1;
        line[to][from] = 1;
    }
    visited[v] = 1;
    dfs(v);

    cout << '\n';
    fill_n(visited, 1001, 0);
    visited[v] = true;
    bfs(v);
    return 0;
}

 

DFS (dept-first search) : 시작 vertex에서 시작하여 해당 vertex에서 도달 가능한 vertex를 recursive하게 방문하는 방법

-> 이미 방문한 vertex를 재방문 하지 않기 위해 visited라는 이름을 가진 array로 이미 방문한 vertex의 목록을 관리한다.

 

BFS (Breadth-First Search) : 시작 vertex에서 시작하여 해당 vertex와 거리가 가까운 순서대로 방문하는 방법

==  두 vertex간의 path에 존재하는 edge 수가 가까운 순서대로 방문하는 방법

-> 다음에 처리할 vertex를 queue로 관리한다.

-> distance array는 시작 vertex에서 해당 vertex 간의 거리를 저장한다. == unweighted 가정

-> adjacency list를 사용할 경우 time comlexity는 O(m+n)이다.