[c++]백준 1260번 : DFS와 BFS

문제 : 백준 1260번 _ DFS와 BFS

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
2 초	128 MB	87845	28912	16832	31.543%

문제

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

입력

첫째 줄에 정점의 개수 N(1 ≤ N ≤ 1,000), 간선의 개수 M(1 ≤ M ≤ 10,000), 탐색을 시작할 정점의 번호 V가 주어진다. 다음 M개의 줄에는 간선이 연결하는 두 정점의 번호가 주어진다. 어떤 두 정점 사이에 여러 개의 간선이 있을 수 있다. 입력으로 주어지는 간선은 양방향이다.

출력

첫째 줄에 DFS를 수행한 결과를, 그 다음 줄에는 BFS를 수행한 결과를 출력한다. V부터 방문된 점을 순서대로 출력하면 된다.

나의 답

1. 처음에 아무것도 모르고 구현한 답이다. (보지 말고 두번째 답으로 넘어가도 좋다.)

/*
    2020-03-20 우희은
    BFS, DFS algorithm
*/
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>

using namespace std;

set<int> arr[10001];
set<int> num_list;

void makeLine(int a, int b) {
    arr[a].insert(b);
    arr[b].insert(a);
}

void setNumList(int num) {
    for (int i = 1; i < num+1; i++) {
        num_list.insert(i);
    }
}
/*
vector<int> quickSorting(vector<int>&v) {
    vector<int> result;
    vector<int>::iterator iter;
}
*/

void qsort(vector<int>&v, int s, int e) {
    int pivot = v[s];
    int bs = s, be = e;
    while (s < e) {
        while (pivot <= v[e] && s < e) e--;
        if (s > e) break;
        while (pivot >= v[s] && s < e) s++;
        if (s > e) break;
        swap(v[s], v[e]);
    }
    swap(v[s], v[e]);
    if (bs < s)
        qsort(v, bs, s - 1);
    if (be > e)
        qsort(v, s + 1, be);
}

void BFS(vector<int> bfs_list) { 
    set<int>::iterator iter;
    vector<int>::iterator bfs_list_iter;
    vector<int> tmp;

    if (num_list.empty()) {
        return;
    }

    for (bfs_list_iter = bfs_list.begin(); bfs_list_iter!=bfs_list.end(); ++bfs_list_iter) {
        if (num_list.erase(*bfs_list_iter)) {
            cout << *bfs_list_iter << " ";
        }
        int j = 0;
        for (iter = arr[*bfs_list_iter].begin(); iter != arr[*bfs_list_iter].end(); ++iter) {
            int x = *std::next(arr[*bfs_list_iter].begin(), j++);
            if (find(tmp.begin(), tmp.end(), x)==tmp.end()) {
                tmp.push_back(x);
            }
        }
    }

    if (tmp.size() == 0) { // 연결된 간선이 없는 경우
        return;
    }

    qsort(tmp, 0, tmp.size()-1);
    BFS(tmp);
}

void DFS(int start) {
    set<int>::iterator iter;
    set<int> tmp;

    if (num_list.empty()) { // 모든 점을 들렀으면 return
        return;
    }
    if (num_list.erase(start)) { // 이미 들른 정점이거나 start가 비어있는 경우 return (*)
        cout << start << " ";
    }else {
        return;
    }

    for (iter = arr[start].begin(); iter != arr[start].end(); ++iter) { // 연결된 간선이 없으면 한 번 더 재귀를 거쳐 (*) 표시된 곳에서 처리
        DFS(*iter);
    }
}

int main() {
    int n, m, v;
    cin >> n >> m >> v;

    for (int i = 0; i < m; i++) {
        int n1, n2;
        cin >> n1 >> n2;
        makeLine(n1, n2);
    }

    setNumList(n);
    DFS(v);

    cout << endl;

    vector<int> tmp_v;
    tmp_v.push_back(v);
    setNumList(n);
    BFS(tmp_v);
}

1)BFS 구현 방식

DFS는 재귀로 구현하는 측면에서 똑같이 생각했지만, BFS를 어떻게 구현해야할지 감이 오지 않았다. 그래서 BFS도 재귀로 구현하되 한꺼번에 자료구조에 넣는 방식을 활용했는데 어떻게 보면 큐를 한 단계씩 쪼개서 사용한 것이라고 보면 될 것 같다. 문제는 큐 자료구조 하나로 해결될 방식을 엄청난 조건을 줘야 해야해서 효율성이 극히 줄었다는 점이다. (이러한 방식 때문에 sorting 코드가 필요하기도 했다.)

2)기저 사례

처음에 바보같이 기저 사례를 전체 노드 (1~N)를 모두 순회하는 것도 포함시켰다. 원래 기저 사례는 연결된 다음 노드가 없거나 연결된 노드를 이미 모두 들렀을 경우이다.

3)이미 들른 노드 체크 방식

대부분의 코드에서 check라는 배열을 n크기만큼 만들어서 거기에 들렀으면 1을 표시하게 해두었다. 2번의 잘못된 생각을 한 이후 1~N까지의 전체 노드를 모두 없앴다는 걸 쉽게 알기 위해 check를 num_list라는 set 자료 구조로 구현하였다. 노드에 도달하면 해당 숫자를 num_list에서 삭제하는 방식이다.

 

 

<여기서부터 봐주세요>

2. BFS, DFS에 대한 이론 공부 후 다시 구현한 코드

/*
    2020-03-20 우희은
    BFS, DFS algorithm
*/

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <queue>

using namespace std;

set<int> arr[1001];
set<int> num_list;

void makeLine(int a, int b) { // 간선 생성
    arr[a].insert(b);
    arr[b].insert(a);
}

void setNumList(int num) {
    for (int i = 1; i < num+1; i++) {
        num_list.insert(i);
    }
}

void BFS(int start) { 
    queue<int> bfs_q;
    set<int>::iterator iter;
    bfs_q.push(start);

    while (bfs_q.size()) {
        int tmp = bfs_q.front();
        bfs_q.pop(); // 노드 queue에서 제외
        if (num_list.erase(tmp)) { // 노드를 이미 방문했음을 표시
            cout << tmp << " "; // 노드 프린트
            for (iter = arr[tmp].begin(); iter != arr[tmp].end(); iter++) {
                if (num_list.find(*iter) != num_list.end()) {
                    bfs_q.push(*iter);
                }
            }
        }
    }


}

void DFS(int start) {
    set<int>::iterator iter;
    set<int> tmp;

    if (num_list.erase(start)) { // 이미 들른 정점이거나 start가 비어있는 경우 return (*)
        cout << start << " ";
    }else {
        return;
    }

    for (iter = arr[start].begin(); iter != arr[start].end(); ++iter) { // 연결된 간선이 없으면 한 번 더 재귀를 거쳐 (*) 표시된 곳에서 처리
        DFS(*iter);
    }
}

int main() {
    int n, m, v;
    cin >> n >> m >> v;

    for (int i = 0; i < m; i++) { // 그래프 만들기
        int n1, n2;
        cin >> n1 >> n2;
        makeLine(n1, n2);
    }

    setNumList(n); 
    DFS(v);

    cout << endl;

    setNumList(n);
    BFS(v);
}

불필요한 코드를 없애고 구현하니 훨씬 간결해졌다.

노드와 간선들로 이루어진 그래프 구조는 set 요소들을 가지는 배열(전역변수 arr)로 나타내었다. index 0은 사용하지 않으며 1부터 N까지의 index를 사용하여 이 요소들은 각 노드를 표현한다. 각각의 index에 있는 set 자료구조는 해당 노드와 연결되어있는 다른 노드의 인덱스를 저장하고 있으며, 중복되지 않고 오름차순으로 정렬하기 위해 set 자료구조를 사용하였다.

set 자료구조는 중복되지 않지만 오름차순인지는 확실치 않다. (아직 나도 무슨 말인지 모르겠음. 공부하기.)

https://stackoverflow.com/questions/15479928/why-is-the-order-in-dictionaries-and-sets-arbitrary/26099671#26099671

 DFS는 거의 모든 코드가 그렇듯 재귀함수로 구현했으며, 이 문제의 특성 상 연결된 간선이 없는 노드도 있을 수 있으므로 그 조건에 대한 처리도 따로 해주었다. (주석으로 표시되어있음)

 

 BFS는 queue라는 자료구조 라이브러리를 import 하여 구현하였다. 큐에 들르는 노드마다 차례로 넣고 하나씩 꺼내면서 해당 노드와 연결된 노드 중 아직 들르지 않은 노드를 큐에 넣어준다. 이런 알고리즘을 큐가 빌 때까지 반복한다.

 

 DFS, BFS 코드에서 이미 들른 노드인지를 알기 위해 처리한 조건은 num_list.erase(value)의 값이 1인지이다. set이라는 자료구조를 활용해서 특정 노드를 들를 때마다 num_list라는 배열에서 해당 index를 삭제하는 연산을 수행하는데 이미 들른 노드이면 해당 연산에서 삭제한 노드 수가 0이 돼버린다.

 

 이 연산을 사용하면 만일 tmp가 삭제되면 안되는 경우는 다시 num_list.insert(value)를 해주어야하는데, 그렇게 되면 쓸모없는 연산이 많아지는 꼴이므로 그냥 num_list.find(value) != num_list.end()를 쓰면된다. set 자료구조의 find 연산은 해당 value가 존재하면 존재하는 곳의 주소를 반환하고, 존재하지 않으면 set 자료구조의 end() 위치를 반환한다. (end() 위치는 마지막 요소 다음 주소 값이다.)

 

 

 이렇게 DFS, BFS를 구현해보았는데 자주 나오는 알고리즘인만큼 더 많은 코드를 찾아보고 최대한 손에 익게 자주 반복해보아야겠다. c++을 이용한다면 자료구조가 워낙 잘되어있어 빠르게 작성할 수 있는 코드일 듯 하다.