[1260번] DFS와 BFS (feat: 동적할당 오버헤드 및 고정크기배열)

https://www.acmicpc.net/problem/1260

1260번: DFS와 BFS

 

다음 문제는 dfs와 bfs의 가장 기초적인 문제다. 

 

문제 풀이법은 딱히 중요한건 아닌 것 같고, 이 문제를 사실 9개월 전에 한번 풀었다가 감이 죽은 지금 다시 한번 풀었는데 메모리랑 실행시간이 너무 크게 비교가 돼서...(물론 9개월 전 코드가 더 아름다웠다.) 마음이 아파서 왜 그런지 비교해보도록 하겠다.

 

실화니...? 9개월전에 더 똑똑했어!!!

9개월 전 똑똑했던 나의 코드

#include <iostream>
#include <queue>
#include <vector>
#include <algorithm>
#define MAX 10001

using namespace std;

int n, m, v;
vector<int> graph[MAX];
bool visited[MAX] = {false};

void dfs(int start) {
    visited[start] = true;
    cout << start << " ";

    // Sort the neighbors in ascending order
    sort(graph[start].begin(), graph[start].end());

    for (int i = 0; i < graph[start].size(); i++) {
        int y = graph[start][i];
        if (!visited[y]) {
            dfs(y);
        }
    }
}

void bfs(int start) {
    queue<int> q;
    bool visited[MAX] = {false};

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int x = q.front();
        q.pop();
        cout << x << " ";

        // Sort the neighbors in ascending order
        sort(graph[x].begin(), graph[x].end());

        for (int i = 0; i < graph[x].size(); i++) {
            int y = graph[x][i];
            if (!visited[y]) {
                q.push(y);
                visited[y] = true;
            }
        }
    }
}

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

    for (int i = 0; i < m; i++) {
        int k, l;
        cin >> k >> l;
        graph[k].push_back(l);
        graph[l].push_back(k);
    }

    dfs(v);
    cout << endl;
    bfs(v);

    return 0;
}

 

9개월 전의 똑똑했던 나는 Define을 즐겨 썼었다!! 특히나 크기가 정해져있지 않은 문제에서 MAX치 값을 땅땅땅 박아놓으면 오히려 더 이득이 많은 경우가 있다고 생각했다. 그래서 그래프도, 방문 횟수도 전역변수로 MAX로 박아버렸다. MAX를 써 고정크기 배열을 생성하였다.

 

안타까운 오늘 짠 내 코드...

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;

void dfs(int v, vector<vector<int>> graph, vector<bool>& visit){
    visit[v] = true;
    cout << v << " ";
    for (int i = 0; i < graph[v].size(); i++)
    {
        int y = graph[v][i];
        if (!visit[y]) dfs(y,graph,visit);
    }
}

void bfs(int v, vector<vector<int>> graph, vector<bool> visit){
    queue<int> q;

    q.push(v);
    visit[v] = true;

    while (!q.empty()) {
        for (auto a: graph[q.front()]) {
            if (!visit[a]) {
                visit[a] = true;
                q.push(a);
            }
        }

        cout << q.front()<<" ";
        q.pop();
    }
}

int main() {
    int n,m,v; // n: 정점의 개수, m: 간선의 개수, v: 시작할 정점의 번호
    cin >> n >> m >> v;
    vector<vector<int>> graph(n+1);

    for (int i = 0; i < m; i++) {
        int x, y;
        cin >> x >> y;
        graph[x].push_back(y);
        graph[y].push_back(x);
    }

    for(auto &vec : graph) {
        sort(vec.begin(), vec.end());
    }

    vector<bool> visit(n+1,false);
    dfs(v, graph, visit);
    cout<<endl;

    vector<bool> visit2(n+1,false);
    bfs(v, graph, visit2);
}

 

오늘 짠 내 코드는.. 구현하는데 눈이 멀어서 메모리나 실행시간 관점에서 딱히 고려하지 않은 것 같다. 특히나 vector사이즈를 동적으로 할당하고 있으며, 함수에 넘기는 인자들도 확연히 다르다. 더 많고 무겁게 느껴진다.

 

고정크기 배열 VS 악마의 vector

고정크기 배열을 써야한다고 자료구조 시간에 최근에 배워서 사용해봤던 것 같다. 지금은 왜 까먹었는지... 하핫

 

9개월 전	오늘
고정 크기 배열	동적 메모리 할당

 

1. 오늘 코드는 추가적인 메모리 오버헤드가 발생한다.

vector는 동적 메모리 할당을 사용하기에, 동적 할당에는 특히 고정 크기 배열에 비해서 추가적인 메모리 오버헤드가 발생한다.

또한, 이런 메모리 오버헤드가 각 정점마다 별도로 할당되기 때문에(vector<vector<int>>) 오버헤드가 누적되면서 상당히 많은 메모리를 사용하게 된다. 그야말로 무서운 코드다.

 

2. 오늘 코드는 캐시 효율성이 우수하지 못하다.

또한, 고정 크기 배열은 연속된 메모리 블록에 데이터를 저장하기 때문에 캐시 효율성이 우수하다. 반면, vector<vector<int>>의 경우 각 요소는 다른 메모리 위치에 할당될 가능성이 있다. 따라서 캐시미스가 더 자주 발생할 수 있다. 

 

 

3. 동적 할당과 해제의 비용

전공시간에 배웠겠지만, vector에 요소를 추가하거나 제거에 따라서 메모리 할당과 해제가 시간이 많이 소요된다. 특히나 vector의 크기가 변경될 때마다 재할당이 일어날 수 있는데, 이는 실행시간을 증가시킬 수 있다.

 

4. 초기화 비용

오늘 코드에서는 또한 vector<bool>을 n+1로 초기화하는데도 많은 시간이 소요될 수 있다.

 

5. 함수 호출 비용

오늘 코드는 dfs, bfs함수에 graph, visit인자를 전달하게 된다. 또한 심지어 graph는 참조지만 vector은 크기가 클 경우에 전달 과정에서도 비용이 추가적으로 발생한다. 

 

 

정리

종합적으로 봤을 때, 동적메모리 할당과 관리, 캐시 사용의 효율성, 그리고 함수 호출과 인자 전달 방식 등이 조금 크게 결과에 작용했던 것 같다. 프로그래밍 대회에서는 이런 비용을 최소화하기 위해서 고정크기 배열과 같은 기술들을 선호하게 된다!!!

 

앞으로 종만북 읽으면서 체화해보쟈~! 오랜만에 풀었으니 그럴 수 있지! 앞으로 안그러면 된다 ㅎㅎ

 

파이팅 지민!!