1260번 - DFS와 BFS(c++)

🗒 1260번 문제

📌 BFS(너비 우선 탐색), DFS(깊이 우선 탐색) 모두 구현해야 하는 문제 ❗️

✅ 참고 사이트

1️⃣ 깊이 우선과 너비 우선 모두 사용해서 구현해보자 !!

2️⃣ DFS가 뭐예요..?
A. 루트 노드(혹은 다른 임의의 노드)에서 시작해서 다음 분기(branch)로 넘어가기 전에 해당 분기를 완벽하게 탐색하는 방법

3️⃣ 넓게(wide) 탐색하기 전에 깊게(deep) 탐색하는 것이다.

4️⃣ 사용하는 경우: 모든 노드를 방문 하고자 하는 경우에 이 방법을 선택한다.

5️⃣ BFS보다 간단하다 -> stack 사용

6️⃣ 자기 자신을 호출하는 순환 알고리즘의 형태를 가지고 있다
-> 어떤 노드를 방문했었는지 여부를 반드시 검사 해야 한다는 것이다. 이를 검사하지 않을 경우 무한루프에 빠질 위험이 있다.

7️⃣ 방문하는 방법
1. a 노드(시작 노드)를 방문한다.
2. 방문한 노드는 방문했다고 표시한다.
3. a와 인접한 노드들을 차례로 순회한다.
4. a와 인접한 노드가 없다면 종료한다.
5. a와 이웃한 노드 b를 방문했다면, a와 인접한 또 다른 노드를 방문하기 전에 b의 이웃 노드들을 전부 방문해야 한다.
6. b를 시작 정점으로 DFS를 다시 시작하여 b의 이웃 노드들을 방문한다.
7. b의 분기를 전부 완벽하게 탐색했다면 다시 a에 인접한 정점들 중에서 아직 방문이 안 된 정점을 찾는다.
8. 즉, b의 분기를 전부 완벽하게 탐색한 뒤에야 a의 다른 이웃 노드를 방문할 수 있다는 뜻이다.
9. 아직 방문이 안 된 정점이 없으면 종료한다.
10. 있으면 다시 그 정점을 시작 정점으로 DFS를 시작한다.

8️⃣ 이번 문제는 수행 결과를 방문된 점 순서대로 출력해야 하기 때문에 아직 안 들어간 곳에 들어가면 바로 cout 시켜줬다.

➰ 코드로 나타낸 1260번 ➰

#include <iostream>
#include <stack>
#include <queue>
#include <algorithm>

using namespace std;

vector<int> nodes[1001];
queue<int> q;
stack<int> s;
bool entered_dfs[1001];
bool entered_bfs[1001];
int node, edge, startNode;

//stack 사용
void dfs() {
    s.push(startNode);
    // 첫 번째 노드는 일단 stack에 들어가고 본다.
    
    while (!s.empty()) {
        int n = s.top();
        
        if(entered_dfs[n] == true) {
            s.pop(); // 이미 들어간 곳 pop 시키기
            continue;
        }
        else {
            s.pop(); // 안 들어간 곳이기에 출력시켜주고 true로 만들기
            cout << n << " ";
            entered_dfs[n] = true;
        }
        
        for (int i = nodes[n].size() - 1; i >= 0; i--) {
            int m = nodes[n][i];
            // 인접 노드 찾아서 다른 false면 push하기
            
            if (entered_dfs[m] == false) s.push(m);
        }
    }
    cout << endl;
}

//queue 사용
void bfs() {
    q.push(startNode);
    // 첫 번째 노드는 일단 queue에 들어가고 본다.
    
    while (!q.empty()) {
        int n = q.front();
        
        if (entered_bfs[n] == true) {
            q.pop();
            continue;
        }
        else {
            q.pop();
            cout << n << " ";
            entered_bfs[n] = true;
        }
        
        for (int i = 0; i < nodes[n].size(); i++) {
            int j = nodes[n][i];
            
            if (entered_bfs[j] == false) {
                q.push(j);
            }
        }
    }
    cout << endl;
}

int main() {
    cin >> node >> edge >> startNode;
    
    for (int i = 0; i < edge; i++) {
        int n, m;
        cin >> n >> m;
        nodes[n].push_back(m);
        nodes[m].push_back(n);
    }
    
    for (int i = 0; i <= node; i++) {
        sort(nodes[i].begin(), nodes[i].end());
    }
    
    dfs();
    bfs();
    // 두 함수의 다른 점은 for문이 돌아가는 시작점과 마지막점
}