[그래프] 백준 1260 c++ / Nested Functions, 정적배열과 동적배열, memset ..

몇 가지 궁금점

• 그래프 탐색 결과를 출력해야 하는데 문득 main 함수 내에 dfs, bfs 함수를 정의할 수 있을지 궁금해졌음

-> 바보같은 생각 걍 main 밖에 함수 정의하고 cout 하면 됨

 

그래도 중첨 함수 선언에 대해 알아보자

Nested Functions, 중첩 함수

Nested functions이란 다른 함수의 내부에 정의된 함수이다.

nested function 예시) 

foo (double a, double b)
{
  double square (double z) { return z * z; }

  return square (a) + square (b);
}

GNU C 확장에선 지원되지만 GNU C++에서는 지원되지 않는다고.

 

참고: https://gcc.gnu.org/onlinedocs/gcc/Nested-Functions.html 

Nested Functions (Using the GNU Compiler Collection (GCC))

 

? 또 어떤 글에선 C++에서 된다는데 

다시 알아보고 추후 추가할 것

 

• 정적 배열을 최댓값으로 선언해놓는 게 빠른지 아니면 동적배열을 할당받아 각 칸을 0으로 채우는 게 빠른지 ?

=> 정적 배열이 빠르긴 하지만 동적배열과의 속도 차이가 그렇게 신경쓸 만한 정도는 아니라고 함

• new로 2차원배열을 동적할당 받았을 때 for문 돌아서 초기화하는 방법이랑 memset 쓰는 방법 중 뭐가 더 빠른지?

=> 대체로 memset이 빠르다고 함

---

정답 제출 코드 

#include <iostream>
#include <string.h>
#include <vector>

using namespace std;

int N, M, V;
int **arr;
int visited_dfs[1001] = {0, };
int visited_bfs[1001] = {0, };
vector <int> next_bfs;

void dfs(int r)
{
    // 방문한 정점 출력 후 방문 처리
    cout << r << " ";
    visited_dfs[r] = 1;
    
    for(int i=1; i<N+1; i++)
    {
        if(arr[r][i] && !visited_dfs[i])
            dfs(i);
    }
}

void bfs(int r)
{
    next_bfs.erase(next_bfs.begin());

    if(!visited_bfs[r])
    {
        cout << r << " ";
        visited_bfs[r] = 1;
    }


    for(int i=1; i<N+1; i++)
    {
        if(arr[r][i] && !visited_bfs[i])
        {
            cout << i << " ";
            visited_bfs[i] = 1;
            next_bfs.push_back(i);
        }
    }

    if(!next_bfs.empty())
        bfs(next_bfs.front());
    
}

int main()
{
    cin >> N >> M >> V;
    
    arr = new int*[N+1];
    for(int i=0; i<N+1; i++)
    {
        arr[i] = new int[N+1];
        memset(arr[i], 0, sizeof(int)*(N+1));
    }
        
    for(int i=0; i<M; i++)
    {
        int r, c;
        cin >> r >> c;
        arr[r][c] = 1;
        arr[c][r] = 1;
    }

    dfs(V);
    cout << endl;
    next_bfs.push_back(V);
    bfs(V);

    return 0;
}

좀 지저분하다고 생각했는데 다른 분들의 코드를 찾아보니 비슷비슷한듯

 

bfs가 생각보다 오래 걸렸음

처음에는 next_bfs로 다음 방문 정점을 정해주지 않아서 무한 루프가 돌아버렸음