6주차(DFS와 BFS) - [C++]백준1260 DFS와 BFS

07 Apr 2022 in Study on Algorithm

백준1260 DFS와 BFS 링크

문제

예제 입력

---

코드

#include <cstring>  //memset(check, false, sizeof(check)); 초기화
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
using namespace std;

vector<int> arr[1001];
bool visit[1001];

void dfs(int st) { 
    visit[st] = true;
    cout << st << ' ';
    for (int i = 0; i < arr[st].size(); i++) {
        int next = arr[st][i];
        if (visit[next] == false) {
            dfs(next);
        }
    }
}

void bfs(int st) {
    queue<int> q;
    visit[st] = true;
    q.push(st);
    
    while (!q.empty()) {
        int node = q.front();
        q.pop();
        cout << node << ' ';
        for (int i = 0; i < arr[node].size(); i++) {
            int next = arr[node][i];
            if (visit[next] == false) {
                visit[next] = true;
                q.push(next);
            }
        }
    }
}

int main(void)
{
    ios_base::sync_with_stdio(0);
    cin.tie(0); //cin 실행속도 향상

    int n, m, st;
    cin >> n >> m >> st;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        arr[u].push_back(v); //인접행렬
        arr[v].push_back(u);
    }

    for (int i = 1; i <= n; i++) { // 각 정점마다 최소
        sort(arr[i].begin(), arr[i].end());
    }

    dfs(st); // 깊이우선
    cout << '\n';
    for (int i = 1; i <= 1000; i++) // 초기화
        visit[i] = false;
    bfs(st); // 너비우선
}

설명

이 문제는 그래프가 주어지고 탐색을 할때 DFS와 BFS로 수행하는 결과를 출력하는 것입니다. C++ STL(표준 템플릿 라이브러리)에서 vector와 Queue를 사용하여 구현했습니다. 주어진 그래프를 입력 받아 시작점을 기준으로 탐색을 하는데 각 정점의 최소정점을 다음 정점으로 잡기때문에 정렬를 해주고 먼저 DFS는 1 -> 2 -> 4 -> 3으로 일단 한 방향으로 끝까지 가는 방식으로 하며 BFS는 1 -> 2 -> 3 -> 4으로 현재 시점에서 할 수 있는 모든 것을 확인하는 방식으로 합니다.

-pair<자료형, 자료형> 변수명; : 하나의 변수에 2가지 값을 저장함

<algorithm>
-sort(시작, 끝, 비교함수) : 배열의 크기만큼 정렬

<queue>
-queue<자료형> 변수명; : 큐 자료구조 사용

---

결과