[BFS/DFS] C++로 구현해보기

C++언어도 연습해보기루 했다.

C++에서는 이차배열을 동적할당으로 받아주기가 까다로워서 그냥 최대값 N을 미리 주고 선언을해서

for문을 통해 조절해서 실행해준다.

그리고 지역변수로는 할당해줄수 있는 사이즈가 좀 제한적이다. (이건 에디터설정이라고 함.)

그래서 전역변수로 설정해주면 스택오버플로우가 발생하지 않았다.

전반적으로 자바와 똑같았고, 다른 점은 pop()함수가 void형이라는것과 top()으로 그 기능을 구현해준다는 것.

빼고는 다 똑같았다. ㅋ.ㅋ 

그리고 dfs구현 할때 간과하기 쉬운것 2가지를 발견했다.

1.for문을 반대로 돌아야 원하는 결과를 얻을 수 있다(오름차순으로 구할 수 있다는 말)

2.while문을 돌때 이미 방문한 점에 대해서는 넘겨주어야 한다. 다른 그래프에서 그 그래프와 연결되어있다면 중복으로 방문할 수 있기 때문. 꺼내면서 방문을 해주기때문에 두번 꺼낼수 있다는 소리다. 꺼내고 방문되어있다면 pass 해주자!

 

 

#include <iostream>
#include <queue>
#include <stack>
 
using namespace std;
 
int N, M, V;
int a[1001][1001];
bool isV[1001];
queue<int> q1;
stack<int> s1;
 
 
void bfs(int v) {
    isV[v] = true;
    q1.push(v);
    
    while (!q1.empty()) {
        int vv = q1.front();
        q1.pop();
        cout << vv << " ";
        for (int i = 1; i <= N; i++) {
            if (a[vv][i] == 1 && !isV[i]) {
                q1.push(i);
                isV[i] = true;
            }
        }
    }
}
 
void dfs(int v) {
 
    s1.push(v);
 
    while (!s1.empty()) {
        int vv = s1.top();
        s1.pop();
        if (isV[vv]) continue;
        isV[vv] = true;
        cout << vv << " ";
        for (int i = N; i >= 1; i--) {
            if (a[vv][i] == 1 && !isV[i]) {
                s1.push(i);
            }
        }
    }
}
 
int main()
{
    cin >> N >> M >> V;
    for (int i = 1; i <= M; i++) {
        int col, row;
        cin >> col >> row;
        a[col][row] = 1;
        a[row][col] = 1;
    }
 
    dfs(V);
    for (int i = 1; i <= N; i++) { isV[i] = false; }
    cout << endl;
    bfs(V);
    
    return 0;
}