1260_DFS와 BFS (C++)

1260번: DFS와 BFS

#include <iostream>
#include <cstring> //memset
#include <queue>
using namespace std;

bool visited[1001] = {false};
int arr[1001][1001];
int n, m, startV;

void dfs(int v){
    cout << v << " ";
    visited[v] = true;

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

void bfs(int v){
    queue<int> q;
    q.push(v);
    visited[v] = true;

    while(!q.empty()){
        int x = q.front();
        cout << x << " ";
        q.pop();

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

int main(){
    cin >> n >> m >> startV;

    for(int i=0; i<m; i++){
        int v1, v2;
        cin >> v1 >> v2;
        arr[v1][v2] = arr[v2][v1] = 1;
    }

    dfs(startV);
    
    cout << endl;
    memset(visited, false, sizeof(visited)); //visited[] 초기화
    
    bfs(startV);
    
    return 0;
}

 

DFS : 깊이 우선 탐색

 

①연결된 점이 있으면 ②그 점과 연결된 또다른 점을 찾는다.

이 두가지를 재귀로 반복하며 찾는다.

 

 

 

BFS : 너비 우선 탐색

 

①각 정점과 연결된 모든 점을 파악하고, ②그 연결된 점에서 연결된 모든 점을 파악한다.

연결된 모든 점을 큐에 넣고, ①이 끝나면 큐에서 점을 pop해서 ②를 수행한다.

 

 

 

 

---

 

 

 

• memset

• (배열/벡터의 모든값) 초기화 시 사용됨
• 헤더 : <cstring>
• memset(메모리 시작 주소, 초기화값, 변경할 메모리 크기)
• 여기서 초기화 값 = 1Byte 를 의미한다. -> bool형(true/false), char형, 숫자0
• 배열 - memset(배열 이름, 초기화값, sizeof(배열이름))
• 예) memset(arr, flase, sizeof(arr)); 
•      memset(arr, 1, sizeof(arr));