백준 1260: DFS와 BFS

📃 문제: 백준 1260(DFS와 BFS)

1260번: DFS와 BFS

그래프를 DFS로 탐색한 결과와 BFS로 탐색한 결과를 출력하는 프로그램을 작성하시오. 단, 방문할 수 있는 정점이 여러 개인 경우에는 정점 번호가 작은 것을 먼저 방문하고, 더 이상 방문할 수 있는 점이 없는 경우 종료한다. 정점 번호는 1번부터 N번까지이다.

 

 

🥈 난이도: 실버 2

 

 

 

😲 사용한 개념: DFS(깊이우선탐색), BFS(너비우선탐색)

DFS(깊이 우선 탐색)	BFS(너비 우선 탐색)
Stack	Queue

 

 ☝️ DFS란?

1️⃣ 탐색 시작 노드 정보를 스택에 삽입하고  pop연산과 동시에 방문처리 한다.
2️⃣ 스택 내 최상단 노드에 방문하지 않은 노드가 있다면 그 인접 노드 정보를 스택에 삽입하고

pop연산과 동시에 방문 처리한다.
만일 방문하지 않은 인접 노드가 없다면 스택 내 최상단 노드를 꺼낸다.(빈 스택 상태)
3️⃣ 아직 방문처리되지 않은 수 중 가장 작은 수를 push하여, 2번의 과정을 더 이상 수행할 수 없을 때까지 반복한다.

 

 

✌️ BFS란?

1️⃣ 탐색 시작 노드 정보를 큐에 삽입하고  pop연산과 동시에 방문처리 한다.
2️⃣ pop한 노드의 인접 노드들 중 방문처리가 되지 않은 노드 정보를 큐에 삽입하고 방문 처리한다.
3️⃣ 인접노드 push가 끝나면, 최상단 노드를 pop하고, 2~3번 과정을 큐가 empty상태가 될 때까지 반복한다.

 

 

 

📖 풀이 사고 과정

 

 

 

👩‍💻 구현 코드(c++ 사용)

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
vector <vector<int>> A;
queue<int> myQueue;
bool visited[10001] = { false, };

void DFS(int num) {
    if (visited[num]) return;
    visited[num] = true;
    cout << num << " ";
    //여러 노드에 접근할 수 있다면, 작은 수부터
    sort(A[num].begin(), A[num].end());
    for (int n : A[num]) {
        if (!visited[n]) DFS(n);
    }
}

void BFS(int num) {
    myQueue.push(num);
    while (!myQueue.empty()) {
        int top = myQueue.front();
        myQueue.pop();
        visited[top] = true;
        cout << top << " ";
        sort(A[top].begin(), A[top].end());
        for (int n : A[top]) {
            if (!visited[n]) myQueue.push(n);
            //큐에 이미 들어간 애도 방문처리
            visited[n] = true;
        }
    }  
}

int main(void) {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int start, N, M, s, e;
    cin >> N >> M >> start;
    //index 1부터 시작하는 것 주의
    A.resize(N+1);
   
    for (int i = 0; i < M; i++) {
        cin >> s >> e;
        A[s].push_back(e);
        A[e].push_back(s);
    }

    DFS(start);
    cout << endl;
    for (int i = 1; i <= N; i++)visited[i] = false;
    BFS(start);

    return 0;
}